图论专题

B-最短路

题面
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。

输入保证至少存在1条商店到赛场的路线。

Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 1
1 2 33 3
1 2 5
2 3 5
3 1 20 0

Sample Output

3
2

题目分析
最短路问题模板题，用dijkstra+优先队列算法或Floyd算法模板即可解题

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define INF 1000000000using namespace std;struct edge{int to,cost;
};typedef pair<int,int > P;//first是最短距离，second是顶点编号 int N,M;
vector<edge> G[105];   //G[v]存与v点相连的边 int d[105];            //d[v]记录到v点最短距离 void dijkstra(int s)
{//通过指定greater<P>参数，堆按照first从小到大的顺序取出值priority_queue< P , vector<P> , greater<P> > que;fill(d+1,d+N+1,INF);d[s] = 0;que.push( P(0,s) );while(!que.empty()){P p=que.top();que.pop();int v=p.second;//v为从v点出发 if(d[v]<p.first) continue;for(int i=0;i< G[v].size();i++){edge e=G[v][i];if(d[e.to]>d[v]+e.cost){   			//遍历与v相接边找出与v下一点d[e.to]=d[v]+e.cost;			//最短距离放至vector中 que.push( P(d[e.to],e.to) );	//【vector 按first小到大取出值】 }}}} int main()
{while(~scanf("%d%d",&N,&M)){if(N==0&&M==0)break;for(int i=1;i<=N;i++)G[i].clear();while(M--){int A,B,C;scanf("%d%d%d",&A,&B,&C);edge E;E.to=B;E.cost=C;G[A].push_back(E);E.to=A;G[B].push_back(E);}dijkstra(1);printf("%d\n",d[N]);}return 0;
}