记录编号	140783	评测结果	AAAAAAAAAAAAAAAA
题目名称	[USACO Jan11]道路与航线	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.413 s
提交时间	2014-11-25 10:44:28	内存使用	1.70 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
#include<stack>
#define CL(x) memset(x,0,sizeof(x))
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std;
typedef long long LL;
int read(){
    int ret=0,f=1;
    char x=getchar();
    while(!(x>='0' && x<='9')){if(x=='-')f=-1;x=getchar();}
    while(x>='0' && x<='9') ret=ret*10+x-'0', x=getchar();
    return ret*f;
}

typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
const int MAXN=25000+10;
const LL INF=1e12;
int N,R,P,S;
vector<PIL> G[MAXN];
void init(){
	N=read(), R=read(), P=read(), S=read();
	rep(i,1,R){
		int u=read(), v=read(), c=read();
		G[u].push_back(PIL(v,c));
		G[v].push_back(PIL(u,c));
	}
	rep(i,1,P){
		int u=read(), v=read(), c=read();
		G[u].push_back(PIL(v,c));
	}
}

int low[MAXN],belong[MAXN];
int pre[MAXN];int dc;
vector<int> ps[MAXN],FA[MAXN];
int bn;

stack<int> SS;
void tarjan(int u,int fa){
	pre[u]=low[u]=++dc;
	SS.push(u);
	rep(i,0,(int)G[u].size()-1){
		int v=G[u][i].first;
		if(belong[v]){FA[belong[v]].push_back(u); continue; }
		if(pre[v]){
			low[u]=min(low[u],pre[v]);
		}else{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		if(belong[v]) FA[belong[v]].push_back(u);
	}
	if(low[u]==pre[u]){
		bn++;
		while(SS.size()){
			int x=SS.top(); SS.pop();
			ps[bn].push_back(x);
			belong[x]=bn;
			if(x==u) break;
		}
	}
}

LL d[MAXN];
bool vis[MAXN];
void dij(int block){
	priority_queue<PLI,vector<PLI>,greater<PLI> >q;
	rep(i,0,(int)ps[block].size()-1){
		int p=ps[block][i];
		if(d[p]<INF) q.push(PLI(d[p],p));
	}
	while(q.size()){
		int u=q.top().second; q.pop();
		if(vis[u]) continue;
		else vis[u]=true;
		rep(i,0,(int)G[u].size()-1){
			int v=G[u][i].first; LL c=G[u][i].second;
			if(d[v]>d[u]+c){
				d[v]=d[u]+c;
				//cout<<d[19]<<endl;
				if(belong[v]==block) q.push(PLI(d[v],v));
			}
		}
	}
}

bool have_sol[MAXN];
void sol(int block){
	if(have_sol[block]) return;
	else have_sol[block]=true;
	rep(i,0,(int)FA[block].size()-1){
		int f=FA[block][i]; sol(belong[f]);
	}
	dij(block);
}
void work(){
	CL(vis);
	tarjan(S,0);
	CL(vis);
	rep(i,1,N) d[i]=INF;
	d[S]=0;
	rep(i,1,bn) sol(i);
	rep(i,1,N){
		if(d[i]>=INF) printf("NO PATH\n");
		else printf("%d\n",d[i]);
	}
}

int main(){
	freopen("roadplane.in","r",stdin);
	freopen("roadplane.out","w",stdout); 
	init();
	work();
	//print();
	return 0; 
}