本文共 2362 字，大约阅读时间需要 7 分钟。
TonyY是一个喜欢到处浪的男人，他的梦想是带着兰兰姐姐浪遍天朝的各个角落，不过在此之前，他需要做好规划。
现在他的手上有一份天朝地图，上面有n个城市，m条交通路径，每条交通路径都是单行道。他已经预先规划好了一些点作为旅游的起点和终点，他想选择其中一个起点和一个终点，并找出从起点到终点的一条路线亲身体验浪的过程。但是他时间有限，所以想选择耗时最小的，你能告诉他最小的耗时是多少吗？
Input
包含多组测试数据。
输入第一行包括两个整数n和m，表示有n个地点，m条可行路径。点的编号为1 - n。
接下来m行每行包括三个整数i, j, cost，表示从地点i到地点j需要耗时cost。
接下来一行第一个数为S，表示可能的起点数，之后S个数，表示可能的起点。
接下来一行第一个数为E，表示可能的终点数，之后E个数，表示可能的终点。
0<S, E≤n≤100000，0<m≤100000，0<cost≤100。
Output
输出他需要的最短耗时。
Sample Input
4 41 3 11 4 22 3 32 4 42 1 22 3 4
Sample Output
1
题意：
这个题就是一个多源最短路的问题。多源最短路的问题可以转换为单源最短路：将所有的起点全部通过一个自己添加的初始点（比如 ‘0’点） 且0点到所有的起点的距离全部为0，然后再添加一个最终点n+1（默认有n个地点），来让所有的可以到达的终点到最终点n+1的距离全部为0，然后找从新起点‘0’到最终点‘n+1’的最短路。
这个题可以使用dijkstra和spfa，但是使用普通的dijkstra的话由于题目中给出的个数都比较大，所以会超时超内存，所以要用堆优化的dijkstra。
（堆优化的dijkstra与spfa是类似的，堆优化的dijkstra用了堆，每次都找出最短的路径来松弛每个边，一下子就可以松弛到最短路径；而spfa是将所有的点都放入队列，顺序来进行松弛，逐渐的趋近最短路）
堆优化的dijkstra算法：
#include #include #include #include #include #include using namespace std;const int maxn=1e5+10;const int inf=0x3f3f3f3f;struct Edge{ int to; int val; bool operator < (const Edge& a)const //重载运算符 ‘<’，变为最小堆 { return val>a.val; } Edge(int a,int b):to(a),val(b){} Edge(){}};int dis[maxn]; //存放起点到达每个点的最短路int vis[maxn];int n,m;vector path[maxn];void dijkstra(){ memset(vis,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); priority_queue queue; dis[0]=0; queue.push(Edge(0,0)); while(!queue.empty()) { Edge tmp=queue.top(); queue.pop(); int a=tmp.to; if(vis[a]==1)continue; vis[a]=1; for(int i=0;i dis[a]+path[a][i].val) { dis[b]=dis[a]+path[a][i].val; Edge e=Edge(b,dis[b]); queue.push(e); } } }}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<=n;i++) path[i].clear(); for(int i=0;i
spfa算法：
#include #include #include #include #include #include using namespace std;const int maxn=1e5+10;const int inf=0x3f3f3f3f;struct Edge{ int to; int val; Edge(int a,int b):to(a),val(b){} Edge(){}};int dis[maxn];int vis[maxn];int n,m;vector path[maxn];void dijkstra(){ memset(vis,0,sizeof(vis)); for(int i=0;i<=n+1;i++) dis[i]=inf; dis[0]=0; queue q; vis[0]=1; q.push(0); while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i dis[x]+val) dis[to]=dis[x]+val; if(!vis[to]) { q.push(to); vis[to]=1; } } }}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i
转载地址：http://mizci.baihongyu.com/