这是昨天POJ校赛的一道题，昨天中午从12点到1点多一直纠结于这道题，后来有社团的乒乓球比赛就没有做了，今天总算把它搞定了Orz..
题目很简单，在一个国家有两个group，记做1和2，N个city，每个city属于1或者2。每两个city间有一定的距离，现在要从city1去city2，问最短
的距离是多少，要求至多只有一次穿越时跨过分属不同group的city。city1总是属于group1，city2总属于group2。
很明显的最短路，但关键是如何建图。可以看到，一共只有两种走法，一种是从city1出发，一直走属于group1的city直到city2，或者一直走属
于group2的city直到city2。我昨天建了两个图来表示两种情况，分别求最短路，然后取小的，结果越写越乱。今天发现其实一次就可以，只要在建
图的时候，如果两个city属于一个group，就建双向图，否则就建从属于group1的city到属于group2的city的单向图。原因很简单，因为两种情况都不会
出现从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);
}
}