|
ing namespace std; #define maxn 550 #define INF 0x3f3f3f3f struct Edge { int from, to, dist; }; struct HeapNode { int d, u; bool operator < (const HeapNode& rhs) const { return d > rhs.d; } }; int n, S, E; vector
edges; vector
G[maxn]; bool vis[maxn]; int d[maxn], p[maxn], p1[maxn], p2[maxn]; void Init(int n) { for(int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void addEdge(int from, int to, int dist) { // 无向图，每条边需要调用两次addEdge edges.push_back((Edge){from, to, dist}); int x = edges.size(); G[from].push_back(x-1); } void Dijkstra(int s) { priority_queue
q; for(int i = 1; i <= n; i++) d[i] = INF; d[s] = 0; memset(vis, false, sizeof(vis)); q.push((HeapNode){0, s}); while(!q.empty()) { HeapNode x = q.top(); q.pop(); int u = x.u; if(vis[u]) continue; vis[u] = true; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u]+e.dist) { d[e.to] = d[u]+e.dist; p[e.to] = G[u][i]; q.push((HeapNode){d[e.to], e.to}); } } } } void printA(int k) { if(k == S) { printf("%d", k); return ; } int t = p1[k]; Edge& e = edges[t]; printA(e.from); printf(" %d", k); } void printB(int k) { if(k == E) { printf(" %d", k); return; } printf(" %d", k); int t = p2[k]; Edge& e = edges[t]; printB(e.from); } int main() { int count = 0; int N, M, K, X, Y, Z, f[maxn], g[maxn]; while(~scanf("%d%d%d", &N, &S, &E)) { if(count++) printf("\n"); n = N; scanf("%d", &M); Init(N); while(M--) { scanf("%d%d%d", &X, &Y, &Z); addEdge(X, Y, Z); addEdge(Y, X, Z); } Dijkstra(S); memcpy(f, d, sizeof(d)); memcpy(p1, p, sizeof(p)); Dijkstra(E); memcpy(g, d, sizeof(d)); memcpy(p2, p, sizeof(p)); scanf("%d", &K); int ans = f[E]; int st = -1, ed = -1; while(K--) { scanf("%d%d%d", &X, &Y, &Z); if(ans > Z+f[X]+g[Y]) { ans = Z+f[X]+g[Y]; st = X; ed = Y; } if(ans > Z+f[Y]+g[X]) { ans = Z+f[Y]+g[X]; st = Y; ed = X; } } if(st == -1) { printA(E); printf("\nTicket Not Used\n"); } else { printA(st); printB(ed); printf("\n%d\n", st); } printf("%d\n", ans); } return 0; }
|