uva 10801 - Lift Hopping(最短路Dijkstra) - c++编程基础

题目大意：有一栋100层的大楼（标号为0~99），里面有n个电梯（不超过5个），以及要到达的层数（aid)，然后是每个电梯走一层所需的时间，再n行就是对应每个电梯可以到达的层数，数量不定。然后每装换一次电梯需要等待60秒，问，最快能多快到达目标层数。

解题思路：这题有点坑啊，一开始是用邻接表+Dijkstra，可是忘记考虑aid = 0的情况，这种情况下所得到的答案不需要减掉60（为了方便计算，每次到达一个楼层时间就+60），可是我没发现这个问题，就换成用邻接矩阵去做，后来发现了aid = 0的情况，可是用邻接矩阵需要注意的是更新g[a][b]的为最小值，即当两个电梯都能满足从a层到b层的时候，要选取小的值做g[a][b]的值。

1.邻接矩阵

#include   
#include   
#include   
const int N = 105;  
const int INF = 0x3f3f3f3f;  
int n, aid, cnt, time[N], d[N];  
int g[N][N];  
  
void add(int a, int b, int s) {  
    int dis = abs(b - a) * s;  
    if (g[a][b] > dis)  
        g[a][b] = g[b][a] = dis;  
}  
  
void init() {  
    for (int i = 0; i < n; i++)  
        scanf("%d", &time[i]);  
  
    memset(d, 0x3f, sizeof(d));  
    memset(g, 0x3f, sizeof(g));  
    d[0] = 0;  
  
    for (int i = 0; i < n; i++) {  
        char ch = '\0';  
        int num[N];  
        for (int j = 0; ch != '\n'; j++) {  
            scanf("%d%c", &num[j], &ch);  
            for (int k = 0; k < j; k++)  
                add(num[j], num[k], time[i]);  
        }  
    }  
}  
  
void solve() {  
    int vis[N];  
    memset(vis, 0, sizeof(vis));  
    for (int i = 0; i < 99; i++) {  
        int x, m = INF, flag = 0;  
        for (int j = 0; j < 100; j++)  
            if (!vis[j] && d[j] < m) { m = d[j], x = j, flag = 1; }  
        if (!flag) return;  
        vis[x] = 1;  
        for (int j = 0; j < 100; j++) {  
            if (!vis[j] && d[j] > d[x] + g[x][j] + 60)  
                d[j] = d[x] + g[x][j] + 60;  
        }  
    }  
}  
  
int main () {  
    while (scanf("%d%d", &n, &aid) == 2) {  
        init();  
        solve();  
        if (aid == 0) printf("0\n");  
        else if (d[aid] != INF) printf("%d\n", d[aid] - 60);  
        else printf("IMPOSSIBLE\n");  
    }  
    return 0;  
}

2.邻接表

#include   
#include   
#include   
const int N = 105;  
const int M = 500005;  
const int INF = 1 << 30;  
int n, aid, cnt, time[N], d[N];  
int first[M], next[M], u[M], v[M], w[M];  
  
void add(int a, int b, int s) {  
    u[cnt] = a;  
    v[cnt] = b;  
    w[cnt] = abs(b - a) * s;  
    next[cnt] = first[u[cnt]];  
    first[u[cnt]] = cnt;  
    cnt++;  
}  
  
void init() {  
    for (int i = 0; i < n; i++)  
        scanf("%d", &time[i]);  
  
    for (int i = 0; i < 100; i++) {  
        first[i] = -1;  
        d[i] = (i == 0   0 : INF);  
    }  
  
    for (int i = 0; i < n; i++) {  
        char ch = '\0';  
        int num[N];  
        for (int j = 0; ch != '\n'; j++) {  
            scanf("%d%c", &num[j], &ch);  
            for (int k = 0; k < j; k++)  
                add(num[j], num[k], time[i]), add(num[k], num[j], time[i]);  
        }  
    }  
}  
  
void solve() {  
    int vis[N];  
    memset(vis, 0, sizeof(vis));  
    for (int i = 0; i < 100; i++) {  
        int x, m = INF;  
        for (int j = 0; j < 100; j++)  
            if (!vis[j] && d[j] < m) { m = d[j], x = j; }  
        vis[x] = 1;  
        for (int j = first[x]; j != -1; j = next[j]) {  
            if (d[x] < INF && d[v[j]] > d[x] + w[j] + 60)  
                d[v[j]] = d[x] + w[j] + 60;  
        }  
    }  
}  
  
int main () {  
    while (scanf("%d%d", &n, &aid) == 2) {  
        init();  
        solve();  
        if (aid == 0) printf("0\n");  
        else if (d[aid] != INF) printf("%d\n", d[aid] - 60);  
        else printf("IMPOSSIBLE\n");  
    }  
    return 0;  
}