A – 最短路 HDU – 2544（模板题）

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的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 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2

无向图！

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++) 
#define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<string,pair<int,int> > pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

const int maxn = 10010;

struct qnode{
	int v;
	int c;
	qnode(int _v = 0, int _c = 0):v(_v),c(_c){}
	bool operator <(const qnode &r) const{ return c>r.c;
	}
};

struct Edge{
	int v,cost;
	Edge(int _v = 0, int _cost = 0):v(_v),cost(_cost){}
};

vector<Edge>E[maxn];
bool vis[maxn];
int dist[maxn];
void Dijkstra(int n, int start){
	memset(vis,false,sizeof(vis));
	for(int i = 1; i <= n; i++)dist[i] = INF;
	priority_queue<qnode>que;
	while(!que.empty())que.pop();
	dist[start] = 0;
	que.push(qnode(start,0));
	qnode tmp;
	while(!que.empty()){
		tmp=que.top();
		que.pop();
		int u = tmp.v;
		if(vis[u])continue;
		vis[u] = true;
		rep(i,0,E[u].size()-1){
			int v=E[tmp.v][i].v;
			int cost=E[u][i].cost;
			if(!vis[v]&&dist[v]>dist[u]+cost){
				dist[v] = dist[u]+cost;
				
				que.push(qnode(v,dist[v]));
			}
		}
	}
}

void addedge(int u, int v, int w){
	E[u].push_back(Edge(v,w));
}

int N,M;
int main(){
	while(~scanf("%d%d",&N,&M)&&N&&M){
		int u,v,w;
		rep(i,0,maxn-1){
			E[i].clear();
		}
		while(M--){
			scanf("%d%d%d", &u,&v,&w);
			addedge(u,v,w);
			addedge(v,u,w);
		}
		Dijkstra(N,1);
		printf("%d\n",dist[N]);
	}
	return 0;
}