题意：给你一个无向带权图，以及一个起始点一个终点。问你从起始点到终点的最短路径。
思路：由于点最多有10000个，所以用裸的dijkstra显然是不行的，又由于边最多为20000条所以mlogn复杂度既可以了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <utility> 7 #include <vector> 8 #include <queue> 9 #include <stack> 10 #define INF 500001 11 #define LEN 20002 12 13 using namespace std; 14 15 typedef pair<int, int> pii; 16 int n, m, st, en, dis[LEN], cnt=1; 17 vector<pii> Map[LEN]; 18 19 void Dijkstra(int vex) 20 { 21 priority_queue<pii, vector<pii>, greater<pii> > q; 22 int vis[LEN] = {0}; 23 memset(vis, 0, sizeof vis); 24 for(int i=0; i<n; i++)dis[i] = (i==vex?0:INF); 25 q.push(make_pair(dis[vex],vex)); 26 while(!q.empty()){ 27 pii nv = q.top();q.pop(); 28 int x = nv.second; 29 if(vis[x]) continue; 30 vis[x] = 1; 31 for(vector<pii>::iterator it = Map[x].begin(); it!=Map[x].end(); ++it){ 32 int y = it->first, v = it->second; 33 if(dis[y]>dis[x]+v){ 34 dis[y] = dis[x]+v; 35 q.push(make_pair(dis[y], y)); 36 } 37 } 38 } 39 } 40 41 int main() 42 { 43 // freopen("in.txt", "r", stdin); 44 45 int T; 46 scanf("%d", &T); 47 while(T--){ 48 scanf("%d%d%d%d", &n, &m, &st, &en); 49 int a, b, val; 50 for(int i=0; i<LEN; i++)Map[i].clear(); 51 for(int i=0; i<m; i++){ 52 scanf("%d%d%d", &a, &b, &val); 53 Map[a].push_back(make_pair(b, val)); 54 Map[b].push_back(make_pair(a, val)); 55 } 56 Dijkstra(st); 57 printf("Case #%d: ", cnt++); 58 if(dis[en]==INF)printf("unreachable "); 59 else printf("%d ", dis[en]); 60 } 61 return 0; 62 }