题目大意：网络中有n个SMTP服务器，有m条电缆将它们相连，每条电缆传输信息需要一定的时间。现在给出信息的起点和终点，计算所需的最小时间。
有权图上的单源最短路问题（Single-Source Shortest Path, SSSP），直接使用Dijkstra算法。
1 #include <cstdio> 2 #include <vector> 3 #include <queue> 4 using namespace std; 5 typedef pair<int, int> ii; 6 typedef vector<ii> vii; 7 #define INF 1e9 8 #define TRvii(c, it) 9 for (vii::iterator it = (c).begin(); it != (c).end(); it++) 10 11 int main() 12 { 13 #ifdef LOCAL 14 freopen("in", "r", stdin); 15 #endif 16 int T; 17 scanf("%d", &T); 18 for (int kase = 1; kase <= T; kase++) 19 { 20 int n, m, s, t; 21 scanf("%d%d%d%d", &n, &m, &s, &t); 22 vector<vii> AdjList(n); 23 for (int i = 0; i < m; i++) 24 { 25 int u, v, weight; 26 scanf("%d%d%d", &u, &v, &weight); 27 AdjList[u].push_back(ii(v, weight)); 28 AdjList[v].push_back(ii(u, weight)); 29 } 30 vector<int> dist(n, INF); 31 dist[s] = 0; 32 priority_queue<ii, vector<ii>, greater<ii> > pq; 33 pq.push(ii(0, s)); 34 while (!pq.empty()) 35 { 36 ii top = pq.top(); 37 pq.pop(); 38 int d = top.first, u = top.second; 39 if (d == dist[u]) 40 TRvii(AdjList[u], it) 41 { 42 int v = it->first, weight = it->second; 43 if (dist[u] + weight < dist[v]) 44 { 45 dist[v] = dist[u] + weight; 46 pq.push(ii(dist[v], v)); 47 } 48 } 49 } 50 if (dist[t] != INF) printf("Case #%d: %d ", kase, dist[t]); 51 else printf("Case #%d: unreachable ", kase); 52 } 53 return 0; 54 }