【2017/3/10】 思路： 法1、本来想法是用一个变量记录flag记录是否跨入了阵营2，若是则令flag = 1,从而不能再回阵营1；样例实现没问题，但通不过测试
法2、把跨阵营的道路设为单向通行，即只能从阵营1走向阵营2
/* 最短路径问题 要求：【路线最多只能有一条路连接两个不同阵营】 start = 1, end = 2 ,且城市1总是阵营1,城市2总是阵营2 */ #include<cstdio> #include<algorithm> #define INF 0x3fffffff using namespace std; int edge[610][610]; int visit[660]; int dist[660]; int side[660]; int flag; //只能跨越不同阵营一次 int main(){ int n, m, a, b, t; while(scanf("%d", &n) != EOF){ if(0 == n) break; scanf("%d", &m); flag = 0; //初始化 for(int i = 0; i <= n; i++){ for(int j = 0; j <= n; j++){ edge[i][j] = INF; } edge[i][i] = 0; } for(int i = 1; i <= m; i++){ scanf("%d%d%d", &a, &b, &t); edge[a][b] = edge[b][a] = t; } for(int i = 1; i <= n; i++)//阵营 scanf("%d", &side[i]); for(int i = 1; i <= n; i++){//跨阵营线路只单向通行 for(int j = 1; j <= n; j++){ if(edge[i][j] != INF){ if(1 == side[i] && 2 == side[j]) edge[j][i] = INF; if(1 == side[j] && 2 == side[i]) edge[i][j] = INF; } } } for(int i = 0; i <= n; i++){ visit[i] = 0; dist[i] = edge[1][i]; } //如何实现不能跨越两个阵营两次 visit[1] = 1; for(int i = 1; i <= n; i++){ int min = INF, key = 1; for(int j = 2; j <= n; j ++){ if(0 == visit[j] && min > dist[j]){ //已跨入阵营2，不能回去了 // if(1 == side[j] && 1 == flag) continue; key = j; min = dist[j]; } } // if(2 == side[key]) flag = 1; //跨入阵营2 visit[key] = 1;//加入此点 for(int j = 2; j <= n; j++){//更新最短路径长度 if(0 == visit[j] && dist[j] > dist[key] + edge[key][j]) dist[j] = dist[key] + edge[key][j]; } }//for-i 加点 if(INF == dist[2]) printf("-1\n"); else printf("%d\n", dist[2]); } return 0; }