P207 最短路径

这样写答案不对

#include <iostream>

using namespace std;

const int mod = 100000;
const int INF = 100000000;
const int N = 100;

int n, m;
int path[N][N];
int dis[N];
int vis[N];

void init(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            path[i][j] = INF;
        }
        dis[i] = INF;
    }
}

void Djikstra(int s){
    int i, j;
    for(i = 0; i < n; i++){
        dis[i] = path[s][i];
        vis[i] = 0;
    }
    dis[s] = 0;
    vis[s] = 1;
    int mindis, minnode;
    for(i = 0; i < n; i++){
        mindis = INF;
        minnode = 0;
        for(j = 0; j < n; j++){
            if(!vis[j] && mindis > dis[j]){
                minnode = j;
                mindis = dis[j];
            }
        }
        if(mindis == INF) break;
        vis[minnode] = 1;
        for(j = 0; j < n; j++){
            if(!vis[j] && dis[j] > dis[minnode] + path[minnode][j]){
                dis[j] = (dis[minnode] + path[minnode][j]);
            }
        }
    }
}

int main(){
    int from, to;
    while(cin >> n >> m){
        init();
        int len = 1;
        for(int i = 0; i < m; i++){
            cin >> from >> to;
            if(path[from][to] > len) path[from][to] = path[to][from] = len;

            len = len * 2;
            len = len % mod;
        }
        Djikstra(0);
        for(int i = 1; i < n; i++){
            if(dis[i] == INF) printf("-1\n");
            else printf("%d\n", dis[i] % mod);
        }
    }
}

注意到第k条路径的长度为2^K，则第k条路径的长度会大于前k-1条路径的总和。
由此我们可知两个推断：
（1）在添加第k条路径时，如果路径k连接的两个城市A 、B已经通过其他路径间接的连通了，那么第k条路径绝对不是AB间的最短路径（第k条路径之后的路径也不可能有比当前AB路径更短的路径了，因为第k条路径的长度会大于前k-1条路径的总和）
（2）在添加第k条路径时，如果路径k连接的两个城市A 、B是第一次被连通了（也就是说此前没有任何路径能连通AB，包括通过多条路径间接连通），那么路径k就是AB之间的最短距离了，因为以后不可能存在更短的路径连接AB，以后的单条路径只会越来越长。
通过上述的推断，我们可以利通过建立一个最小连通树的同时算出0号城市到各个城市的最小路径。
具体的算法：
（1）构造一个并查集，每个城市指向自己，二维数组d记录城市之间的距离，初始化为-1不可达，d[i][i]初始化为0
（2）取第一条路径，第一条路径连接了城市a、b，城市a、b间最短路径就是第一条路径，然后把a、b合并在一个集合里
（3）再取一条路径，
（一）如果这条边连接的城市c、d，已经在同一个集合里了（即已经联通了），那么当前的路径一定不是cd之间的最短路径了，忽略之（理由是推断（1）），继续看下一条路径。
(二)如果这条路径连接的城市c、d不在同一个集合里（之前没有联通过），很好，这条路径是cd之间的最短路径（理由是推断（2））；除此之外我们还可以看看通过这条路径能不能让c集合里的城市到d集合里的城市之间的路径更短呢？即是不是d[i][j]>(d[i][C]+dist+d[D][j]) ?(注意i和C一个集合，D和j一个集合)，如果是的话可以更新一下这个值。
（4）重复（3）直到所有路径都处理过了
0号城市到各个城市i的最小路径结果就是d[0][i]了

这样写AC

#include <iostream>
#include <stdio.h>
#include <memory.h>

using namespace std;

const int mod = 100000;
const int INF = 100000000;
const int N = 102;

int n, m;
int path[N][N];
int father[N];
int vis[N];

void init(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            path[i][j] = INF;
        }
        path[i][i] = 0; //对角线
        father[i] = i;
        vis[i] = 0;
    }
}

int find(int x){
    if(x != father[x]){
        father[x] = find(father[x]);
    }
    return father[x];
}

int main(){
    int from, to;
    while(cin >> n >> m){
        init();
        int len = 1;
        for(int i = 0; i < m; i++){
            cin >> from >> to;
            int x = find(from);
            int y = find(to);
            if(x != y){
                //由于代价特点，后面的大于前面所有代价之和，这样一旦连通，后面的在连接也没有意义
                father[x] = y;
                path[from][to] = path[to][from] = len;
            }
            len = len * 2;
            len = len % mod;
        }
        vis[0] = 1;
        int i, j;
        int mindis, minnode;
        for(i = 0; i < n; i++){
            mindis = 123123123;
            minnode = 0;
            for(j = 1; j < n; j++){
                if(!vis[j] && mindis > path[0][j]){
                    minnode = j;
                    mindis = path[0][j];
                }
            }
            vis[minnode] = 1;
            for(j = 1; j < n; j++){
                if(!vis[j] && path[0][j] > path[0][minnode] + path[minnode][j]){
                    path[0][j] = path[0][minnode] + path[minnode][j];
                }
            }
        }
        for(i = 1; i < n; i++){
            if(path[0][i] == INF) printf("-1\n");
            else printf("%d\n", path[0][i] % mod);
        }
    }
}