HDU 2680 Choose the best route 最短路问题
题目描述：Kiki想去他的一个朋友家，他的朋友家包括所有的公交站点一共有n 个，一共有m条线路，线路都是单向的，然后Kiki可以在他附近的几个公交站乘车，求最短的路径长度是多少。
解题报告：这道题的特点就是有多个起点，但是这并不影响我们使用迪杰斯特拉来解这道题，和前面出现的一个题目一样，我们可以增加一个虚拟的起点，然后令所有的真实的起点到这个虚拟的起点的距离都赋为1，然后就成功的转化成了单源的最短路问题了，并且是单个终点，然后用迪杰斯特拉就OK了，值得注意的就是这题里面的路线都是单向的，即所给出的图的有向图。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 const int MAX = 1000+5,INF = 0xfffff; 5 int map[MAX][MAX],T[MAX],visit[MAX],n,m,s,e,w; 6 int main() { 7 int a,b,len; 8 while(scanf("%d%d%d",&n,&m,&e)!=EOF) { 9 n++; 10 s = n; 11 for(int i = 1;i<=n;++i) { 12 T[i] = INF; 13 for(int j = 1;j<=n;++j) 14 map[i][j] = INF; 15 } 16 for(int i = 1;i<=m;++i) { 17 scanf("%d%d%d",&a,&b,&len); 18 map[a][b] = std::min(len,map[a][b]); 19 } 20 21 scanf("%d",&w); //没有起点与终点相同的情况 22 while(w--) { 23 scanf("%d",&a); 24 map[a][s] = map[s][a] = 1; 25 } 26 memset(visit,0,sizeof(visit)); 27 T[s] = 0; 28 T[0] = INF; 29 while(1) { 30 for(int i = 1;i<=n;++i) 31 if(!visit[i]&&(T[s]+map[s][i])<T[i]) 32 T[i] = T[s]+map[s][i]; 33 visit[s] = 1; 34 bool flag = 1; 35 s = 0; 36 for(int i = 1;i<=n;++i) 37 if(!visit[i]&&T[i]<T[s]) { 38 s = i; 39 flag = 0; 40 } 41 if(flag) 42 break; 43 } 44 printf("%d ",T[e]>INF-5? -1:T[e]-1); 45 } 46 return 0; 47 }