這是昨天POJ校賽的一道題，昨天中午從12點到1點多一直糾結于這道題，后來有社團的乒乓球比賽就沒有做了，今天總算把它搞定了Orz..
題目很簡單，在一個國家有兩個group，記做1和2，N個city，每個city屬于1或者2。每兩個city間有一定的距離，現(xiàn)在要從city1去city2，問最短
的距離是多少，要求至多只有一次穿越時跨過分屬不同group的city。city1總是屬于group1，city2總屬于group2。
很明顯的最短路，但關鍵是如何建圖。可以看到，一共只有兩種走法，一種是從city1出發(fā)，一直走屬于group1的city直到city2，或者一直走屬
于group2的city直到city2。我昨天建了兩個圖來表示兩種情況，分別求最短路，然后取小的，結果越寫越亂。今天發(fā)現(xiàn)其實一次就可以，只要在建
圖的時候，如果兩個city屬于一個group，就建雙向圖，否則就建從屬于group1的city到屬于group2的city的單向圖。原因很簡單，因為兩種情況都不會
出現(xiàn)從2到1的情況。建好圖然后就簡單了，注意無解的情況。
#include<stdio.h>
#include<string.h>
#define INF 0x1f1f1f1f
#define M 602
int map[M][M],dis[M],team[M];
bool flag[M];
void dijkstra(int s,int n)
{
int i,j,k,md,temp;
memset(dis,0x1f,sizeof(dis));
memset(flag,false,sizeof(flag));
dis[s]=0;
for(i=1;i<n;i++){
md=INF;
for(j=1;j<=n;j++){
if(!flag[j]&&dis[j]<md){
md=dis[j];
temp=j;
}
}
if(temp==2) break;
flag[temp]=true;
for(j=1;j<=n;j++)
if(!flag[j]&&map[temp][j]+md<dis[j])
dis[j]=md+map[temp][j];
}
if(dis[2]<map[1][1])printf("%d\n",dis[2]);
else printf("-1\n");
}
int main()
{
int i,j,k,n,m,p,q;
while(scanf("%d",&n),n){
scanf("%d",&m);
memset(map,0x1f,sizeof(map));
for(j=1;j<=m;j++){
scanf("%d%d%d",&p,&q,&k);
map[p][q]=map[q][p]=k;
}
for(j=1;j<=n;j++)
scanf("%d",&team[j]);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++){
if(team[i]==team[j]) //如果是一個group，不用管
continue;
else if(team[i]==1&&team[j]==2) //如果一個是1一個是2，則建單向邊
map[j][i]=map[1][1];
else if(team[i]==2&&team[j]==1) //同上
map[i][j]=map[1][1];
}
dijkstra(1,n);
}
}