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;
}