题目
http://acm.hdu.edu.cn/showproblem.PHP?pid=2544
代码
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int INF = 1000000000;
const int max_v = 110;
const int max_e = 10010;
struct edge {
int to,cost;
};
vector<edge> eg[max_v];
int d[max_v];
bool used[max_v];
typedef pair<int,int> P;
int e,v;
int main()
{
while(scanf("%d%d",&v,&e) && v) {
for(int i = 0 ; i < max_v ; i ++) {d[i] = INF;used[i] = false;}
d[1] = 0;
for(int i = 0 ; i < max_v ; i ++) eg[i].clear();
for(int i = 1 ; i <= e ; i ++) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge d;
d.to = b;d.cost = c;
eg[a].push_back(d);
d.to = a;
eg[b].push_back(d);
}
//Dijkstra
priority_queue< P,vector<P>,greater<P> > que;
que.push(P(0,1));
while(!que.empty()) {
P p = que.top();
que.pop();
int v = p.second;
if(used[v]) continue;
used[v] = true;
for(int i = 0 ; i < eg[v].size() ; i ++) {
edge ee = eg[v][i];
if(d[ee.to] > d[v] + ee.cost) {
d[ee.to] = d[v] + ee.cost;
que.push(P(d[ee.to],ee.to));
}
}
}
printf("%d
",d[v]);
}
return 0;
}
多敲！
