坑爹啊 INF开大了要错,还没有PE
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<stack> #include<queue> #include<algorithm> using namespace std; const int MAXN = 1007; const int INF = 1 << 27; struct Edge { int from, to, dist; Edge() {} Edge(int from, int to, int dist):from(from), to(to), dist(dist) {} }; struct HeapNode { int d, u; HeapNode(int d, int u):d(d), u(u) {} bool operator < (const HeapNode & hn) const { return d > hn.d; } }; struct Dijkstra { int n, m; vector<Edge> edges; vector<int> G[MAXN]; bool done[MAXN]; int d[MAXN]; int p[MAXN]; void init(int n) { this->n = n; for(int i = 1; i <= n; i++) G[i].clear(); edges.clear(); } void addedge(int u, int v, int d) { edges.push_back( Edge(u, v, d) ); G[u].push_back( edges.size() - 1); } void dijkstra(int s) { memset(done, 0, sizeof(done)); for(int i = 1; i <= n; i++) d[i] = INF; priority_queue<HeapNode> pq; pq.push(HeapNode(0, s)); d[s] = 0; p[s] = -1; while( !pq.empty()) { HeapNode u = pq.top(); pq.pop(); if(done[u.u]) continue; done[u.u] = true; int i, sz = G[u.u].size(); for(i = 0; i < sz; i++) { Edge v = edges[G[u.u][i]]; if(d[v.to] > d[u.u] + v.dist) { d[v.to] = d[u.u] + v.dist; p[v.to] = u.u; pq.push( HeapNode(d[v.to], v.to)); } } } } }Dijk; Edge Eg[MAXN]; int dA[MAXN], dB[MAXN]; int pA[MAXN], pB[MAXN]; int main() { int n, s, e, id = 0; while(~scanf("%d%d%d", &n, &s, &e)) { Dijk.init(n); int i, u, v, d, k; scanf("%d", &k); for(i = 0; i < k; i++) { scanf("%d%d%d", &u, &v, &d); Dijk.addedge(u, v, d); Dijk.addedge(v, u, d); } scanf("%d", &k); for(i = 0; i < k; i++) scanf("%d%d%d", &Eg[i].from, &Eg[i].to, &Eg[i].dist); Dijk.dijkstra(s); for(i = 1; i <= n; i++) { dA[i] = Dijk.d[i]; pA[i] = Dijk.p[i]; } Dijk.dijkstra(e); for(i = 1; i <= n; i++) { dB[i] = Dijk.d[i]; pB[i] = Dijk.p[i]; } int ans = dA[e], te = e, tt; bool noused = true; for(i = 0; i < k; i++) { int tmp = dA[Eg[i].from] + dB[Eg[i].to] + Eg[i].dist; if( tmp < ans) { ans = tmp; noused = false; te = Eg[i].from; tt = Eg[i].to; } tmp = dA[Eg[i].to] + dB[Eg[i].from] + Eg[i].dist; if(tmp < ans) { ans = tmp; noused = false; te = Eg[i].to; tt = Eg[i].from; } } if(id++) puts(""); int ttt = te; stack<int> path; while(te != -1) { path.push(te); te = pA[te]; } printf("%d", path.top()); path.pop(); while( !path.empty()) { printf(" %d", path.top()); path.pop(); } if( !noused) { te = tt; while(te != -1) { printf(" %d", te); te = pB[te]; } printf("\n%d\n", ttt); } else puts("\nTicket Not Used"); printf("%d\n", ans); } return 0; }