记录编号	298613	评测结果	AAAAAAAAAA
题目名称	[USACO Feb07] 奶牛聚会	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-08-22 10:56:29	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct node{
	int x,dis;
	node(int x,int dis):x(x),dis(dis){}
	bool operator<(const node &x)const{
		return dis>x.dis;
	}
};
int n,m,p,a[maxn][maxn],dis1[maxn],dis2[maxn],x,y;
bool vis[maxn];
void dijkstra1(int);
void dijkstra2(int);
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("sparty.in","r",stdin);
	freopen("sparty.out","w",stdout);
#endif
	scanf("%d%d%d",&n,&m,&p);
	memset(dis1,63,sizeof(dis1));
	memset(dis2,63,sizeof(dis2));
	while(m--){
		scanf("%d%d",&x,&y);
		scanf("%d",&a[x][y]);
	}
	dijkstra1(p);
	dijkstra2(p);
	y=0;
	for(int i=1;i<=n;i++)y=max(y,dis1[i]+dis2[i]);
	printf("%d",y);
	return 0;
}
void dijkstra1(int x){
	memset(vis,0,sizeof(vis));
	priority_queue<node>heap;
	heap.push(node(x,0));
	while(!heap.empty()){
		node t=heap.top();
		heap.pop();
		x=t.x;
		if(vis[x])continue;
		//printf("%d %d\n",x,t.dis);
		vis[x]=true;
		dis1[x]=t.dis;
		for(int i=1;i<=n;i++)if(a[x][i]&&!vis[i])
			heap.push(node(i,t.dis+a[x][i]));
	}
}
void dijkstra2(int x){
	//printf("\n\n");
	memset(vis,0,sizeof(vis));
	priority_queue<node>heap;
	heap.push(node(x,0));
	while(!heap.empty()){
		node t=heap.top();
		heap.pop();
		x=t.x;
		if(vis[x])continue;
		//printf("%d %d\n",x,t.dis);
		vis[x]=true;
		dis2[x]=t.dis;
		for(int i=1;i<=n;i++)if(a[i][x]&&!vis[i])
			heap.push(node(i,t.dis+a[i][x]));
	}
}
int hzoier=MAIN();
int main(){;}