记录编号	528384	评测结果	EEEEEEEEEE
题目名称	[USACO Feb07] 奶牛聚会	最终得分	0
用户昵称	tat	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2019-03-07 20:11:04	内存使用	0.00 MiB

#include <bits/stdc++.h>
#define MA 100000
using namespace std;
int n,x,m;
int sh[1001][1001]={0},r=0;
int main(int argc, char** argv) {
	freopen("sparty.in","r",stdin);
	freopen("sparty.out","w",stdout);
		scanf("%d %d %d\n",&n,&m,&x);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			sh[i][j]=MA; 
		}
	}
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d %d %d\n",&a,&b,&c);
		sh[a][b]=c;
	}
	//cout<<"fuc";
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i!=j){
					if(sh[i][k]+sh[k][j]<sh[i][j]){
						sh[i][j]=sh[i][k]+sh[k][j];
					}
				}
			}
		}
	}
	//cout<<"fuc";
	int r=0;
	for(int i=1;i<=n;i++){
		if(sh[i][x]!=MA&&sh[x][i]!=MA)r=max(r,sh[i][x]+sh[x][i]);
	}
	cout<<r;
	return 0;
	
}