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

Download