這是昨天POJ校賽的一道題，昨天中午從12點(diǎn)到1點(diǎn)多一直糾結(jié)于這道題，后來(lái)有社團(tuán)的乒乓球比賽就沒(méi)有做了，今天總算把它搞定了Orz..
題目很簡(jiǎn)單，在一個(gè)國(guó)家有兩個(gè)group，記做1和2，N個(gè)city，每個(gè)city屬于1或者2。每?jī)蓚€(gè)city間有一定的距離，現(xiàn)在要從city1去city2，問(wèn)最短
的距離是多少，要求至多只有一次穿越時(shí)跨過(guò)分屬不同group的city。city1總是屬于group1，city2總屬于group2。
很明顯的最短路，但關(guān)鍵是如何建圖。可以看到，一共只有兩種走法，一種是從city1出發(fā)，一直走屬于group1的city直到city2，或者一直走屬
于group2的city直到city2。我昨天建了兩個(gè)圖來(lái)表示兩種情況，分別求最短路，然后取小的，結(jié)果越寫(xiě)越亂。今天發(fā)現(xiàn)其實(shí)一次就可以，只要在建
圖的時(shí)候，如果兩個(gè)city屬于一個(gè)group，就建雙向圖，否則就建從屬于group1的city到屬于group2的city的單向圖。原因很簡(jiǎn)單，因?yàn)閮煞N情況都不會(huì)
出現(xiàn)從2到1的情況。建好圖然后就簡(jiǎn)單了，注意無(wú)解的情況。
#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]) //如果是一個(gè)group，不用管
continue;
else if(team[i]==1&&team[j]==2) //如果一個(gè)是1一個(gè)是2，則建單向邊
map[j][i]=map[1][1];
else if(team[i]==2&&team[j]==1) //同上
map[i][j]=map[1][1];
}
dijkstra(1,n);
}
}