题目描述
寒假到了，n 头牛都要去参加一场在编号为 x 的牛的农场举行的派对，农场之间有 m 条有向路，每条路都有一定的长度。
每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这 n 头牛的最短路径（一个来回）中最长的一条路径长度。
输入格式
第一行有三个整数，分别表示牛的数量 n，道路数 m 和派对农场编号 x。
接下来 m 行，每行三个整数 u,v,w，表示存在一条由 u 通向 v 的长度为 w 的道路。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3
输出 #1
10
/** @Description: To iterate is human, to recurse divine.* @Autor: Recursion* @Date: 2022-03-17 12:52:04* @LastEditTime: 2022-03-17 14:45:27*/
#include<bits/stdc++.h>
#define Inf 0x3f3f3f
using namespace std;
int A[1001][1001];
int n,m,x;int main()
{while(cin>>n>>m>>x){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)A[i][j]=Inf;int u,v,w;for(int i=1;i<=m;i++){cin>>u>>v>>w;if(A[u][v]!=Inf)A[u][v]=min(A[u][v],w);A[u][v]=w;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];}// for(int i=1;i<=n;i++){// for(int j=1;j<=n;j++)// cout<<A[i][j]<<" ";// cout<<endl;// } for(int i=1;i<=n;i++)A[i][i]=0;// for(int i=1;i<=n;i++){// for(int j=1;j<=n;j++)// cout<<A[i][j]<<" ";// cout<<endl;// } int max=0;for(int i=1;i<=n;i++)if(A[x][i]+A[i][x]>=max)max=A[x][i]+A[i][x];cout<<max<<endl;}
}