TRAFFICN - Traffic Network
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define MAX 10010
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
const int INF=(int)1e9+7;
vector<ii> gf[MAX],gb[MAX],ga[MAX];
int d[3][MAX];
int m,n,k,s,t;
void minimize(int &x,const int &y) {
if (x>y) x=y;
}
void loadgraph(void) {
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&k);
scanf("%d",&s);
scanf("%d",&t);
FOR(i,1,n) {
gf[i].clear();
gb[i].clear();
ga[i].clear();
}
REP(i,m) {
int u,v,w;
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&w);
gf[u].push_back(ii(v,w));
gb[v].push_back(ii(u,w));
}
REP(i,k) {
int u,v,w;
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&w);
ga[u].push_back(ii(v,w));
ga[v].push_back(ii(u,w));
}
memset(d,0x3f,sizeof d);
}
void dijkstra(int s,vector<ii> g[],int d[]) {
priority_queue<ii,vector<ii>,greater<ii> > q;
while (!q.empty()) q.pop();
d[s]=0;
q.push(ii(0,s));
while (!q.empty()) {
int u=q.top().se;
int w=q.top().fi;
q.pop();
FORE(it,g[u]) if (w+it->se<d[it->fi]) {
d[it->fi]=w+it->se;
q.push(ii(d[it->fi],it->fi));
}
}
}
void process(void) {
dijkstra(s,gf,d[0]);
dijkstra(t,gb,d[1]);
int res=d[0][t];
FOR(i,1,n) FORE(j,ga[i]) minimize(res,d[0][i]+j->se+d[1][j->fi]);
if (res>=INF) printf("-1\n"); else printf("%d\n",res);
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("tmp.txt","r",stdin);
#endif
int tc;
scanf("%d",&tc);
REP(ct,tc) {
loadgraph();
process();
}
return 0;
}