Uva 11374 Airpot Express

坑爹啊 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;
}