P203 畅通工程续

这里的N比较小，所以不用优先队列，用for循环搜索最近的点也能通过，书上的答案是用结构体和优先队列。

#include <iostream>

using namespace std;

const int N = 200;
const int INF = 1000000;

int n, m, s, t;
int map[N][N];
int dis[N];
bool vis[N];

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

void Dijkstra(int s){
    int i, j;
    for(i = 0; i < n; i++){
        dis[i] = map[s][i];
    }
    dis[s] = 0;
    vis[s] = true;
    int mincost, minnode;
    for(i = 0; i < n; i++){
        mincost = INF;
                minnode = 0; //这句有没有都行
        //找到距离s最近的点 
        for(j = 0; j < n; j++){
            if(!vis[j] && mincost > dis[j]){
                minnode = j;
                mincost  = dis[j];
            }    
        }
        if(mincost == INF) break;
        vis[minnode] = true;
        //更新，如果经过minnode会缩短cost则更新。
        for(j = 0; j < n; j++){
            if(!vis[j] && dis[j] > dis[minnode] + map[minnode][j]){
                dis[j] = dis[minnode] + map[minnode][j];
            }
        } 
    }
}

int main(){

    int from, to, cost;
    while(cin >> n >> m){
        init();
        for(int i = 0; i < m; i++){
            cin >> from >> to >> cost;
            if(map[from][to]> cost){
                map[from][to] = cost;
                map[to][from] = cost;
            }    
        }
        cin >> s >> t;
        Dijkstra(s);
        if(dis[t] == INF){
            printf("-1\n");
        }else{
            printf("%d\n", dis[t]);
        }
    }
    return 0;
} 

第一次提交WA是因为，没有注意到可能多次输入同一条路径，这时要判断一下。
下面是没有判断，所以WA的代码

#include <iostream>

using namespace std;

const int N = 200;
const int INF = 1000000;

int n, m, s, t;
int map[N][N];
int dis[N];
bool vis[N];

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

void Dijkstra(int s){
    int i, j;
    for(i = 0; i < n; i++){
        dis[i] = map[s][i];
    }
    dis[s] = 0;
    vis[s] = true;
    int mincost, minnode;
    for(i = 0; i < n; i++){
        mincost = INF;
        //找到距离s最近的点 
        for(j = 0; j < n; j++){
            if(!vis[j] && mincost > dis[j]){
                minnode = j;
                mincost  = dis[j];
            }    
        }
        if(mincost == INF) break;
        vis[minnode] = true;
        //更新，如果经过minnode会缩短cost则更新。
        for(j = 0; j < n; j++){
            if(!vis[j] && dis[j] > dis[minnode] + map[minnode][j]){
                dis[j] = dis[minnode] + map[minnode][j];
            }
        } 
    }
}

int main(){

    int from, to, cost;
    while(cin >> n >> m){
        init();
        for(int i = 0; i < m; i++){
            cin >> from >> to >> cost;
            //if(map[from][to]> cost){
                map[from][to] = cost;
                map[to][from] = cost;
            //}    
        }
        cin >> s >> t;
        Dijkstra(s);
        if(dis[t] == INF){
            printf("-1\n");
        }else{
            printf("%d\n", dis[t]);
        }
    }
    return 0;
}