题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=2544
最短路
Description
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
Input
输入包括多组数据。每组数据第一行是两个整数$N、M（N leq 100，M leq 10000）$，$N$表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为$N$的路口是赛场所在地，$M$则表示在成都有几条路。$N=M=0$表示输入结束。接下来$M$行，每行包括3个整数$A，B，C （1leq A,B leq N,1 leq C leq 1000）$,表示在路口$A$与路口$B$之间有一条路，我们的工作人员需要$C$分钟的时间走过这条路。
Output
输入保证至少存在1条商店到赛场的路线。
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
堆优化的dijkstra求最短路。。。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<vector> 7 #include<queue> 8 #include<map> 9 using std::map; 10 using std::cin; 11 using std::cout; 12 using std::endl; 13 using std::find; 14 using std::sort; 15 using std::pair; 16 using std::vector; 17 using std::multimap; 18 using std::priority_queue; 19 #define pb(e) push_back(e) 20 #define sz(c) (int)(c).size() 21 #define mp(a, b) make_pair(a, b) 22 #define all(c) (c).begin(), (c).end() 23 #define iter(c) decltype((c).begin()) 24 #define cls(arr,val) memset(arr,val,sizeof(arr)) 25 #define cpresent(c, e) (find(all(c), (e)) != (c).end()) 26 #define rep(i, n) for (int i = 0; i < (int)(n); i++) 27 #define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i) 28 const int N = 11000; 29 typedef unsigned long long ull; 30 struct P { 31 int w, v; 32 P(int i = 0, int j = 0) :w(i), v(j) {} 33 inline bool operator<(const P &a) const { 34 return w > a.w; 35 } 36 }; 37 struct Node { int to, w, next; }; 38 int n, m; 39 struct Dijkstra { 40 Node G[N]; 41 int tot, dist[N], head[N]; 42 inline void init() { 43 tot = 0; 44 cls(head, -1), cls(dist, 0x3f); 45 } 46 inline void add_edge(int u, int v, int w) { 47 G[tot] = { v, w, head[u] }; head[u] = tot++; 48 } 49 inline void built(int m) { 50 int u, v, w; 51 rep(i, m) { 52 scanf("%d %d %d", &u, &v, &w); 53 add_edge(u, v, w), add_edge(v, u, w); 54 } 55 } 56 inline void dijkstra(int s) { 57 dist[s] = 0; 58 priority_queue<P> q; 59 q.push(P(0, s)); 60 while (!q.empty()) { 61 P t = q.top(); q.pop(); 62 int u = t.v; 63 if (dist[u] < t.w) continue; 64 for (int i = head[u]; ~i; i = G[i].next) { 65 int &w = dist[G[i].to]; 66 if (w > dist[u] + G[i].w) { 67 w = dist[u] + G[i].w; 68 q.push(P(w, G[i].to)); 69 } 70 } 71 } 72 printf("%d ", dist[n]); 73 } 74 }go; 75 int main() { 76 #ifdef LOCAL 77 freopen("in.txt", "r", stdin); 78 freopen("out.txt", "w+", stdout); 79 #endif 80 while (~scanf("%d %d", &n, &m), n + m) { 81 go.init(); 82 go.built(m); 83 go.dijkstra(1); 84 } 85 return 0; 86 }