意甲冠军：一群奶牛去的地方。去回，然后回去寻找最伟大值。

题解：两遍最短路，结束。邻接矩阵存边能够避免建反图。

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N  1005

#define inf 0x3f3f3f3f

using namespace std;

int map[N][N],n,m,s;

int dist1[N],dist2[N];

bool visit[N];

void dij1()

{

	memset(dist1,0x3f,sizeof(dist1));

	memset(visit,0,sizeof(visit));

	int i,u,v,temp,round;

	dist1[s]=0;

	for(round=1;round<n;round++)

	{

		temp=inf;

		for(i=1;i<=n;i++)

		{

			if(!visit[i]&&temp>dist1[i])

			{

				temp=dist1[i];

				u=i;

			}

		}

		visit[u]=1;

		for(v=1;v<=n;v++)

		{

			dist1[v]=min(dist1[v],dist1[u]+map[u][v]);

		}

	}

	return ;

}

void dij2()

{

	memset(dist2,0x3f,sizeof(dist2));

	memset(visit,0,sizeof(visit));

	int i,u,v,temp,round;

	dist2[s]=0;

	for(round=1;round<n;round++)

	{

		temp=inf;

		for(i=1;i<=n;i++)

		{

			if(!visit[i]&&temp>dist2[i])

			{

				temp=dist2[i];

				u=i;

			}

		}

		visit[u]=1;

		for(v=1;v<=n;v++)

		{

			dist2[v]=min(dist2[v],dist2[u]+map[v][u]);

		}

	}

	return ;

}

int main()

{

//	freopen("test.in","r",stdin);

	int i,a,b,c;

	scanf("%d%d%d",&n,&m,&s);

	memset(map,0x3f,sizeof(map));

	for(i=1;i<=m;i++)

	{

		scanf("%d%d%d",&a,&b,&c);

		map[a][b]=c;

	}

	dij1();

	dij2();

	int ans=0;

	for(i=1;i<=n;i++)ans=max(ans,dist1[i]+dist2[i]);

	printf("%d\n",ans);

	return 0;

}