题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2680
题目大意：一个笨蛋要坐车去朋友家，但坐车呕吐，所以想在最短时间内到达。
测试数据意思：
第一行三个数：n(车站的个数，n<1000) | m(代表车站之间所有线路的总个数) | s(代表离朋友家最近的车站)
下面有m行: p q t 意思是：一条从p到q的线路，花费t时间
m行之后有个数字：w (代表可以在开始时搭乘的车站)
下面w个数W1,W2....Ww就是车站的编号
解题报告：
从题意看，我们可以反过来看。看成是：从要到达的车站s到可以搭车的车站w...反正不管正着看，还是反着看，就是求点到点的最短路径问题，而且没有负权值(为什么要没有负权值呢，下面讲)，明显用dijkstra(混蛋，不懂的话，看下数据结构书p187)。
思路：你想啊笨蛋
如果存在一条从i到j的最短路经(pi,.......pk,pj),那么(p1.......pk)必然是一条从i到k的最短路经，否则的话，(pi.....pk,pj)不可能成为从i到j的最短路径。为了求出最短路径，dijkstra提出了一个按路径长度递增的次序产生最短路径的算法；
什么意思呢？ 大致意思就是：对于原顶点V0,首先选择其直接相邻的顶点中最短的顶点Vi，那么可知：由V0经过Vi到与Vi直接相邻的顶点Vj的最短距离dis[j] = min( map[V0][j] , dis[i] + map[i][j]) 这句最重要了，什么意思呢？就是要么直接到，要么转一下再到。(觉得很熟悉，在动态规划或贪心时，见过)
所以：
假设存在G=<V,E>，源顶点为V0，U={V0},dis[i]记录V0到i的最短距离 ，map[i][j]记录i到j的距离
1.从V-U中dis[i]值最小的顶点i，将i加入到U中；
2.更新与i直接相邻顶点的dis值。(dist[j]=min{map[V0][j],dis[i]+map[i][j]})
3.直到U=V，停止。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 2002 //这个地方太坑爸爸了，按照题目上我设成20002居然没执行函数体，直接return 啦
#define N 1002 //这些看题目数据范围
#define INF 999999
int n,m,s;
int map[M][M]; //map[i][j]表示i到j的权值
int dis[N]; //dis[i] 表示原点s到i的距离
int visit[N]; //顶点是否被访问过
void dijkstra(int s)
{int i,j,k = 0;int min;memset(visit,0,sizeof(visit)); //初始时都没被访问过for(i = 1; i <=n; i++){dis[i] = map[s][i];}visit[s] = 1; //第一个顶点即原点，被访问dis[s] = 0; //s到s 即为0for(i = 1; i < n; i++){min = INF;//找到最小的for (j = 1; j <= n; j++){if ( !visit[j] && dis[j] < min){min = dis[j];k = j; //最小的顶点}}if (min == INF){break;}visit[k] = 1; //k顶点被访问//这里就是比较：直接到还是转一下再到//我猜，你个笨蛋肯定会问：不能转多下吗？//答曰：从源点一个一个向外扩展，具有最优子结构。每个dis[i]都保留着从s到i的最短距离。转多下的情况把它分解开，就知道了for(j = 1; j <= n; j++) {if ( !visit[j] && dis[j] > dis[k] + map[k][j]){dis[j] = dis[k] + map[k][j];}}}return ;
}
int main()
{int i,j;int p,q,t,w;int minx ,ww;while ( scanf("%d %d %d",&n,&m,&s) != EOF){memset(dis,0,sizeof(dis));for (i = 1; i<= n; i++)for(j = 1; j <= n; j ++){map[i][j] = INF;}for(i = 1; i <= m; i++){scanf("%d%d%d",&p,&q,&t);if(t < map[q][p]) //题目上明明说的t <= 1000的，尼玛不加就错。以后保险起见要加啊map[q][p] = t; //注意啊啊啊啊啊啊,因为是把S(目的地)看成源点，所以有向图方向要反过来啊}dijkstra(s);scanf("%d",&w);minx = INF;for (i = 1; i <=w; i++ ) //找到最小的dis{scanf("%d",&ww);if (minx > dis[ww]){minx = dis[ww];}}if ( minx != INF){printf("%d\n",minx);}else{printf("-1\n");}}return 0;
}
然后解释：为什么dijkstra为什么不能有负权值？？？
比如：相邻顶点i，j这两个顶点之间的边map[i][j] < 0，那么当V0到Vi的最短路径为dis[i]时，那dis[j]怎么算呢？
按我们的dijkstra算法该是dist[j]=min{map[V0][j],dis[i]+map[i][j]}那么明显，当计算dis[i]时，i顶点已经加入了最短路径的集合U中，U中的最短路径及其长度是不会再变更的，因为visit[i] 已经被访问过变为1。。。dis[i] 再加上一个负数是小于dis[i]的，而算dis[i]时有可能该有j再到i的(这里具体解释一下：按自己理解，把扩展i，j之前所有的顶点看成a，若a到i权值为10，a到j权值为20，i到j权值为-100，那么接下来a必定要先到i得到dis[i]，这之后dis[i]就不能再更改了，然后再由{a,i}到j，但这时会发现：如果由a到j再到i，那么dis[i]会更小，所以这里就出现了错误。再所以，就不能有负权值啊)。
那如果有负权值，怎么搞呢？
可以用 Bellman-Ford算法。
如何保存路径呢？
倒过来想就好了，比如：从源点a经过很多很多步到达了b，然后经过一步到达了终点c，那么此时我们反着想，倒着走，如果满足
dis[b]+Cost[b][c])==dis[c]这个条件，就说明b必然在路径中。。。。
看代码比较清楚点。。。。
#include <cstdio>
#include <iostream>
#define BIG 5
#include <cstring>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 6
#define INF 1000005
using namespace std;int q[N+1],dis[N+1],vis[N+1],a,b,cnt;
int Cost[N+1][N+1]=
{{0,0,0,0,0,0},{0,0,20,15,INF,INF,INF},{0,2,0,INF,INF,10,30},{0,INF,4,0,INF,INF,10},{0,INF,INF,INF,0,INF,INF},{0,INF,INF,INF,15,0,INF},{0,INF,INF,INF,4,10,0}
};
//int sp[10];
int index = 0;
void dijstra(int u)
{memset(vis,0,sizeof(vis));for (int i=0; i<=N; i++)dis[i]=INF;dis[u]=0;vis[u] =0;for (int i=1; i<N; i++){int _MIN=INF;for (int j=1; j<=N; j++)if (!vis[j] && dis[j]<_MIN){_MIN=dis[j];u=j;}vis[u]=1;for (int j=1; j<=N; j++)if (!vis[j] && dis[j]>dis[u]+Cost[u][j])dis[j]=dis[u]+Cost[u][j];}
}void Getpath(int u)
{q[++cnt]=u;if (u==a){for (int i=cnt; i>1; i--){cout<<q[i]<<"->";// sp[index++] = q[i];}cout<<q[1]<<endl;cnt--;return ;}for (int i=1; i<=N; i++)if (i!=u && dis[i] < INF && (dis[i]+Cost[i][u])==dis[u]){Getpath(i);}cnt--;
}int main()
{printf("输入起点和终点：\n");while (scanf("%d%d",&a,&b)!=EOF){//sp[1] = a;cnt=0;if(a == b){printf("0\n");continue ;}dijstra(a);if(dis[b] >= INF){printf("无路可走~\n");continue;}Getpath(b);}return 0;
}
