P208 I Wanna Go Home

http://poj.org/problem?id=3767
AC代码

#include <iostream>

using namespace std;

const int N = 601;
const int INF = 10000000;

int n, m;
int path[N][N];
int vis[N];
int dis[N];
int leader[N];     //记录城市领导
bool flag;         //记录是否跨过区域

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

void Dijikstra(int s, int t){
    int i, j;
    for(i = 1; i <= n; i++){
        dis[i] = path[s][i];
        vis[i] = 0;
    }
    dis[s] = 0;
    vis[s] = 1;
    int mincost, minnode;
    for(i = 1; i <= n; i++){
        minnode  = 0;
        mincost = INF;
        for(j = 1; j <= n; j++){
            if(!vis[j] && mincost > dis[j]){
                minnode = j;
                mincost = dis[j];
            }
        }
        if(mincost == INF || minnode == t) break;
        vis[minnode] = 1;
        for(j = 1; j <= n; j++){
//             if(!vis[j] && dis[j] > dis[minnode] + path[minnode][j]){
//                 if(leader[j] == leader[minnode]){
//                     dis[j] = dis[minnode] + path[minnode][j];
//                 }else if(leader[j] != leader[minnode] && flag){
//                     dis[j] = dis[minnode] + path[minnode][j];
//                     flag = false;
//                 }
//             }
            if(!vis[j] && !(leader[minnode] == leader[t] && leader[j] != leader[t]) && dis[j] > dis[minnode] + path[minnode][j]){
                dis[j] = dis[minnode] + path[minnode][j];
            }
        }
    }
}

int main(){
    int a, b,t;
    while(cin >> n){
        if(n == 0) break;
        init();
        cin >> m;
        while(m--){
            cin >> a >> b >> t;
            if(path[a][b] > t){
                path[a][b] = path[b][a] = t;
            }
        }
        int tmp;
        for(int i = 1; i <= n; i++){
            cin >> tmp;
            leader[i] = tmp;
        }
        //flag = true;
        Dijikstra(1, 2);
        if(dis[2] == INF) printf("-1\n");
        else printf("%d\n", dis[2]);
    }
}

我自己写的，判断是否能走的地方没写对
（1->1 1->2 2->2）都行，（2->1）不行，所以直接向上面那样写就行。

void Dijikstra(int s, int t){
    int i, j;
    for(i = 1; i <= n; i++){
        dis[i] = path[s][i];
        vis[i] = 0;
    }
    dis[s] = 0;
    vis[s] = 1;
    int mincost, minnode;
    for(i = 1; i <= n; i++){
        minnode  = 0;
        mincost = INF;
        for(j = 1; j <= n; j++){
            if(!vis[j] && mincost > dis[j]){
                minnode = j;
                mincost = dis[j];
            }
        }
        if(mincost == INF || minnode == t) break;
        vis[minnode] = 1;
        for(j = 1; j <= n; j++){
            if(!vis[j] && dis[j] > dis[minnode] + path[minnode][j]){
                if(leader[j] == leader[minnode]){
                    dis[j] = dis[minnode] + path[minnode][j];
                }else if(leader[j] != leader[minnode] && flag){
                    dis[j] = dis[minnode] + path[minnode][j];
                    flag = false;
                }
            }
        }
    }
}