题意很简单，有一个无向图，有2类节点，起点属于I类点，终点属于II类点，求从起点到终点的一条最短路，使得路径最多仅仅有1条边是连接I类点和II类点的。
我的做法是对于I类点和II类点分别求相对于起点和终点的单源最短路径，然后枚举连接I类点和II类点的边，求得最短路径。
但是似乎有更好的方法，就是同类点间的边作双向边处理，而连接I类点与II类点的边作单向边处理，这样只要求得一次最短路，不用枚举了
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