http://acm.hdu.edu.cn/showproblem.php?pid=2544
#include<iostream>
#include<queue>
#include<functional>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e3+;
const int INF = 1e7;
typedef pair<int, int> pll;
struct Node
{
int next;
int s;
Node(int nt, int d):next(nt), s(d){};
};
vector<Node> G[N];
int dis[N];
void dijkstra()
{
priority_queue<pll, vector<pll>, greater<pll> >q;
q.push(pll (,));// 距离 位置
while(!q.empty())
{
pll temp = q.top(); q.pop();
int x = temp.second, ss = temp.first;
if(dis[x]!= ss)
continue;
for(int i = ; i < G[x].size(); i++)
{
int y = G[x][i].next, d = G[x][i].s;
if( dis[y] > dis[x] + d)
{
dis[y]= dis[x]+d;
q.push(pll (dis[y],y));
}
}
}
}
void init(int n)
{
for(int i = ; i <= n; i++)
{
dis[i] = INF;
G[i].clear();
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n, m;
while(cin >> n >> m, n+m)
{
init(n);
int x, y, d;
for(int i = ; i <= m; i++)
{
cin >> x >> y >> d;
G[x].push_back(Node(y,d));
G[y].push_back(Node(x,d));
}
dis[] = ;
dijkstra();
cout << dis[n] << endl;
}
return ;
}