TRAFFICN - Traffic Network

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<vector>
#include<queue>
#include<climits>
#include<algorithm>
using namespace std;

#define N 10000
#define fi first
#define se second
#define TR(v, it) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

int d[N], rd[N], n, m, k, s, t;
vvii g, rg;

void enter() {
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); --s; --t;
	g = vvii(n, vii()); rg = vvii(n, vii());
	for(int i = 0; i < m; ++i) {
		int u, v, l; scanf("%d%d%d",&u,&v,&l); --u; --v;
		g[u].push_back(ii(v, l));
		rg[v].push_back(ii(u, l));
	}
}

void Dijkstra(const vvii &g, int *d, const int &s) {
	fill(d, d+n, INT_MAX); d[s] = 0;
	priority_queue<ii, vii, greater<ii> > qu; qu.push(ii(0, s));
	while(!qu.empty()) {
		int du = qu.top().fi, u = qu.top().se; qu.pop();
		if(du > d[u]) continue;
		TR(g[u], it) {
			int v = it->fi, l = it->se;
			if(du + l < d[v]) qu.push(ii(d[v] = du + l, v));
		}
	}
}

void solve() {
	Dijkstra(g, d, s); Dijkstra(rg, rd, t);
	/*for(int i = 0; i < n; ++i) printf("%d ", d[i]); putchar(10);
	for(int i = 0; i < n; ++i) printf("%d ", rd[i]); putchar(10);*/
	int res = d[t];
	for(int i = 0; i < k; ++i) {
		int u, v, l; scanf("%d%d%d", &u, &v, &l); --u; --v;
		if(d[u] != INT_MAX && rd[v] != INT_MAX)
			res = min(res, d[u] + rd[v] + l);
		if(d[v] != INT_MAX && rd[u] != INT_MAX)
			res = min(res, d[v] + rd[u] + l);
		//res = min(res, min(d[u] + rd[v] + l, d[v] + rd[u] + l));
	}
	printf("%d\n", res == INT_MAX ? -1 : res);
}

int main() {
#ifdef __DONGOCKHANH__
	freopen("input.txt", "r", stdin);
#endif
	int tc; scanf("%d", &tc);
	while(tc--) {
		enter();
		solve();
	}
	return 0;
}

Download