I Wanna Go Home

Dijkstra算法

①对跨越两个阵营的边只保留单向边

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXV = 1010;
const int INF = 1e9;

int n, m;//n城市数、m道路数
int camp[MAXV];//记录阵营
int G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV] = {false};

void init(){
    fill(camp, camp + MAXV, INF);
    fill(G[0], G[0] + MAXV * MAXV, INF);
    fill(d, d + MAXV, INF);
    d[1] = 0;
    fill(vis, vis + MAXV, false);
}

void Dij(){
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return;
        vis[u] = true;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && G[u][j] != INF && d[u] + G[u][j] < d[j]){
                d[j] = d[u] + G[u][j];
            }
        }
    }
}

int main(){
    while(~scanf("%d%d", &n, &m) && n){
        init();
        while(m--){
            int A, B, T;
            scanf("%d %d %d", &A, &B, &T);
            if(G[A][B] > T)
                G[A][B] = G[B][A] = T;
        }
        //输入
        for(int i = 1; i <= n; ++i){
            scanf("%d", &camp[i]);
        }
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <=n; ++j){
                  //只要把不在一个阵营的边设置成有向边即可：camp1->camp2通，camp2->camp1不通
                if(camp[i] == 2 && camp[j] == 1){
                    G[i][j] = INF;
                }
            }
        }
        Dij();
        d[2] != INF ? printf("%d\n", d[2]) : printf("-1\n"); 
    }
    return 0;
}

②在Dijkstra算法中添加一个限制条件，只能从1阵营到2阵营，不能从2阵营到1阵营

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXV = 1010;
const int INF = 1e9;

int n, m;//n城市数、m道路数
int camp[MAXV];//记录阵营
int G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV] = {false};

void init(){
    fill(camp, camp + MAXV, INF);
    fill(G[0], G[0] + MAXV * MAXV, INF);
    fill(d, d + MAXV, INF);
    d[1] = 0;
    fill(vis, vis + MAXV, false);
}

void Dij(){
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return;
        vis[u] = true;
        for(int j = 1; j <= n; j++){
            if(!(camp[u] == 2 && camp[j] == 1)){
                if(!vis[j] && G[u][j] != INF && d[u] + G[u][j] < d[j]){
                    d[j] = d[u] + G[u][j];
                }
            }
        }
    }
}

int main(){
    while(~scanf("%d%d", &n, &m) && n){
        init();
        while(m--){
            int A, B, T;//G[A][B]=T
            scanf("%d %d %d", &A, &B, &T);
            if(G[A][B] > T)
                G[A][B] = G[B][A] = T;
        }
        //输入
        for(int i = 1; i <= n; ++i){
            scanf("%d", &camp[i]);
        }

        Dij();
        d[2] != INF ? printf("%d\n", d[2]) : printf("-1\n"); 
    }
    return 0;
}