基本的最短路问题 就是数据需要稍微处理一下。（N比较大）dijkstra也要优化。不优化应该会T；
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} int N,M,S,T; const int INF = 0x3f3f3f3f; typedef pair<int,int> pii; #define MAXN 20005 priority_queue<pii,vector<pii>,greater<pii> >q; struct node { int v; int w; }; vector <node>G[MAXN];//G[u].v = w present dis[u][v] = w; int d[MAXN]; void read() { scanf("%d%d%d%d",&N,&M,&S,&T); for (int i = 0; i <= N; i++)G[i].clear(); while (M--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); node tmp; tmp.v = v; tmp.w = w; G[u].push_back(tmp); tmp.v = u; tmp.w = w; G[v].push_back(tmp); } } void dijkstra(int st) { memset(d,0x3f,sizeof(d)); d[st] = 0; // printf("%d ",st); while (!q.empty()) q.pop(); q.push(make_pair(d[st],st)); while (!q.empty()) { pii u = q.top(); q.pop(); int x = u.second; if (u.first != d[x]) continue; for (int i = 0; i < (int)G[x].size(); i++) { int v = G[x][i].v, w = G[x][i].w; //printf("%d %d ",v,w); if (d[v] > d[x] + w) { d[v] = d[x] + w; //printf("%d %d ",d[v],v); q.push(make_pair(d[v],v)); } } } } int main() { int num, kase = 1; scanf("%d",&num); while (num--) { read(); dijkstra(S); if (d[T] == INF) printf("Case #%d: unreachable ",kase++); else printf("Case #%d: %d ",kase++,d[T]); } return 0; }