记录编号	361810	评测结果	AAAAAAAAAAAAAAAA
题目名称	[USACO Jan11]道路与航线	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.231 s
提交时间	2017-01-05 07:43:30	内存使用	63.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int _size_=30;
char is[(_size_<<20)+10],os[(_size_<<20)+10],*pi=is,*po=os;
template<class T>inline void readint(T &x){
	static bool neg;
	neg=false;
	x=0;
	while(*pi!='-'&&(*pi<'0'||*pi>'9'))pi++;
	if(*pi=='-'){
		neg=true;
		pi++;
	}
	while(*pi>='0'&&*pi<='9')x=(x<<1)+(x<<3)+(*pi++^'0');
	if(neg)x=-x;
}
template<class T>inline void writeint(T x){
	static int a[25],i;
	if(!x)*po++='0';
	else{
		if(x<0){
			*po++='-';
			x=-x;
		}
		while(x){
			a[++i]=x%10;
			x/=10;
		}
		while(i)*po++=a[i--]^48;
	}
}
const int maxn=25010,maxe=50010;
struct edge{int to,prev,w;}e[maxe<<1];
struct node{
	int x,dis;
	node(int x,int dis):x(x),dis(dis){}
	bool operator<(const node &a)const{return dis>a.dis;}
};
void addedge(int,int,int);
void dfs1(int);
void dfs2(int);
void Dijkstra();
void bfs();
priority_queue<node>heap;
vector<int>a[maxn],G[maxn],W[maxn],G2[maxn];
int last[maxn],len=0,du[maxn]={0},dis[maxn];
bool vis[maxn]={false};
int n,r,p,s,id[maxn]={0},cnt=0,x,y,z;
FILE *fin=fopen("roadplane.in","r"),*fout=fopen("roadplane.out","w");
int main(){
	is[fread(is,sizeof(char),_size_<<20,fin)]='\n';
	readint(n);
	readint(r);
	readint(p);
	readint(s);
	while(r--){
		readint(x);
		readint(y);
		readint(z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	for(int i=1;i<=n;i++)if(!id[i]){
		cnt++;
		dfs1(i);
	}
	while(p--){
		readint(x);
		readint(y);
		readint(z);
		G[x].push_back(y);
		W[x].push_back(z);
		G2[id[x]].push_back(id[y]);
	}
	dfs2(id[s]);
	memset(vis,0,sizeof(vis));
	bfs();
	for(int i=1;i<=n;i++){
		if(dis[i]>=0x3f3f3f3f){
			*po++='N';
			*po++='O';
			*po++=' ';
			*po++='P';
			*po++='A';
			*po++='T';
			*po++='H';
		}
		else writeint(dis[i]);
		*po++='\n';
	}
	fwrite(os,sizeof(char),po-os,fout);
	return 0;
}
void addedge(int x,int y,int z){
	e[++len].to=y;
	e[len].w=z;
	e[len].prev=last[x];
	last[x]=len;
}
void dfs1(int x){
	a[id[x]=cnt].push_back(x);
	for(int i=last[x];i;i=e[i].prev)if(!id[e[i].to])dfs1(e[i].to);
}
void dfs2(int x){
	vis[x]=true;
	for(int i=0;i<(int)G2[x].size();i++){
		du[G2[x][i]]++;
		if(!vis[G2[x][i]])dfs2(G2[x][i]);
	}
}
void Dijkstra(){
	while(!heap.empty()){
		int x=heap.top().x;
		heap.pop();
		if(vis[x])continue;
		vis[x]=true;
		for(int i=last[x];i;i=e[i].prev)if(dis[e[i].to]>dis[x]+e[i].w){
			dis[e[i].to]=dis[x]+e[i].w;
			heap.push(node(e[i].to,dis[e[i].to]));
		}
	}
}
void bfs(){
	memset(dis,63,sizeof(dis));
	queue<int>q;
	q.push(id[s]);
	dis[s]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<(int)a[x].size();i++)if(dis[a[x][i]]<0x3f3f3f3f)heap.push(node(a[x][i],dis[a[x][i]]));
		Dijkstra();
		for(int i=0;i<(int)a[x].size();i++)for(int j=0;j<(int)G[a[x][i]].size();j++){
			dis[G[a[x][i]][j]]=min(dis[G[a[x][i]][j]],dis[a[x][i]]+W[a[x][i]][j]);
			if(!--du[id[G[a[x][i]][j]]])q.push(id[G[a[x][i]][j]]);
		}
	}
}