題意很簡單，有一個無向圖，有2類節(jié)點(diǎn)，起點(diǎn)屬于I類點(diǎn)，終點(diǎn)屬于II類點(diǎn)，求從起點(diǎn)到終點(diǎn)的一條最短路，使得路徑最多僅僅有1條邊是連接I類點(diǎn)和II類點(diǎn)的。
我的做法是對于I類點(diǎn)和II類點(diǎn)分別求相對于起點(diǎn)和終點(diǎn)的單源最短路徑，然后枚舉連接I類點(diǎn)和II類點(diǎn)的邊，求得最短路徑。
但是似乎有更好的方法，就是同類點(diǎn)間的邊作雙向邊處理，而連接I類點(diǎn)與II類點(diǎn)的邊作單向邊處理，這樣只要求得一次最短路，不用枚舉了
1
# include <iostream>
2# include <cstdio>
3# include <cstring>
4using namespace std;
5const int N=800;
6const int M=30000;
7int map[N][N],dis[N];
8bool camp[N],used[N];
9
10void dij(int n,int start)
11
{
12
memset(used,0,sizeof(used));
13 dis[start]=0;
14 while(true)
15
{
16 int minnum=0xfffffff,pos=-1;
17 for(int i=1;i<=n;i++)
18 if(!used[i]&&dis[i]!=-1&&dis[i]<minnum)
19 minnum=dis[i],pos=i;
20 if(pos==-1) break;
21 used[pos]=1;
22 for(int i=1;i<=n;i++)
23 if(!used[i]&&map[pos][i]!=-1&&camp[pos]==camp[i]&&(dis[i]==-1||dis[i]>dis[pos]+map[pos][i]))
24 dis[i]=dis[pos]+map[pos][i];
25
}
26
}
27int main()
28{
29 while(true)
30 {
31 int n,m;
32 scanf("%d",&n);
33 if(!n) break;
34 scanf("%d",&m);
35 memset(map,-1,sizeof(map));
36 while(m--)
37 {
38 int s,e,len;
39 scanf("%d%d%d",&s,&e,&len);
40 if(map[s][e]==-1||map[s][e]>len)
41 {
42 map[s][e]=map[e][s]=len;
43 }
44 }
45 for(int i=1;i<=n;i++)
46 {
47 int t;
48 scanf("%d",&t);
49 switch(t)
50 {
51 case 1:camp[i]=0;break;
52 case 2:camp[i]=1;break;
53 };
54 }
55 memset(dis,-1,sizeof(dis));
56 dij(n,1);
57 dij(n,2);
58 int minroad=0xfffffff;
59 for(int i=1;i<=n;i++)
60 for(int j=1;j<=n;j++)
61 if(camp[i]==camp[1]&&camp[j]==camp[2]&&map[i][j]!=-1&&dis[i]!=-1&&dis[j]!=-1&&dis[i]+dis[j]+map[i][j]<minroad)
62 minroad=dis[i]+dis[j]+map[i][j];
63 if(minroad==0xfffffff)
64 printf("-1\n");
65 else
66 printf("%d\n",minroad);
67 }
68 return 0;
69}
70