5 8 5 1 2 2 1 5 3 1 3 4 2 4 7 2 5 6 2 3 5 3 5 1 4 5 1 2 2 3 4 3 4 1 2 3 1 3 4 2 3 2 1 1
1 -1
题意：一个人，要坐公交去上班。一直有n各站点，m条路线，已知他可以从w各站点出发坐车，求到达目的地s所用的最少时间。如不能到达，则输出-1。
解析：Dijkstra算法，不过直接使用w次Dijkstra，会超时的。下面有两个思路：
1.将这个人的位置设为站点0，然后将站点0和那w个出发点连接在一起，相当于从他家到这些站点的时间为0。然后再使用Dijkstra，输出d[s]即可。
2.利用反向图，因为可以有多个起点，但是只有一个终点，所以反向图的话，相当于只有一个起点，好多个终点了，这样只要使用一次Dijkstra，然后输出w个起点中的最小值即可。
PS：一定要注意公交线路是单向的，一定要建成有向图！！！
AC代码：
思路一
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 1e7 + 2
const int maxn = 1000 + 5;
int n, m;
int w[maxn][maxn], d[maxn], v[maxn];
void dijkstra(int s){
memset(v, 0, sizeof(v));
for(int i=0; i<=n; i++) d[i] = w[s][i];
d[s] = 0;
v[s] = 1;
for(int i=0; i<=n; i++){
int x, m = INF;
for(int y=0; y<=n; y++)
if(!v[y] && d[y] <= m) m = d[x = y];
if(m == INF) break;
v[x] = 1;
for(int y=0; y<=n; y++) d[y] = min(d[y], d[x] + w[x][y]);
}
}
int main(){
#ifdef sxk
freopen("in.txt", "r", stdin);
#endif //sxk
int x, y, z, s, t;
while(scanf("%d%d%d", &n, &m, &s)!=EOF){
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++)
w[i][j] = (i==j ? 0 : INF);
for(int i=0; i<m; i++){
scanf("%d%d%d", &x, &y, &z);
w[x][y] = min(w[x][y], z);
}
scanf("%d", &t);
while(t--){
scanf("%d", &x);
w[0][x] = 0;
}
dijkstra(0);
printf("%d\n", d[s] == INF ? -1 : d[s]);
}
return 0;
}
思路二
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 1e7 + 2
const int maxn = 1000 + 5;
int n, m;
int w[maxn][maxn], d[maxn], v[maxn];
void dijkstra(int s){
memset(v, 0, sizeof(v));
for(int i=0; i<=n; i++) d[i] = w[s][i];
d[s] = 0;
v[s] = 1;
for(int i=0; i<=n; i++){
int x, m = INF;
for(int y=0; y<=n; y++)
if(!v[y] && d[y] <= m) m = d[x = y];
if(m == INF) break;
v[x] = 1;
for(int y=0; y<=n; y++) d[y] = min(d[y], d[x] + w[x][y]);
}
}
int main(){
#ifdef sxk
freopen("in.txt", "r", stdin);
#endif //sxk
int x, y, z, s, t;
while(scanf("%d%d%d", &n, &m, &s)!=EOF){
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++)
w[i][j] = (i==j ? 0 : INF);
for(int i=0; i<m; i++){
scanf("%d%d%d", &x, &y, &z);
w[y][x] = min(w[y][x], z); //处理成反向图
}
dijkstra(s);
scanf("%d", &t);
int ans = INF;
while(t--){
scanf("%d", &x);
ans = min(ans, d[x]); //找最小值
}
printf("%d\n", ans == INF ? -1 : ans);
}
return 0;
}
hdu 2680 Choose the best route （Dijkstra & 反向图）
原文：http://blog.csdn.net/u013446688/article/details/42915199