題目連結:點選打開連結
題目大意:略。
#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=105;
int lens[maxn][maxn];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
mem(lens,INF);
for(int i=0;i<m;i++)
{
int u,v,w; scanf("%d%d%d",&u,&v,&w);
lens[u][v]=lens[v][u]=w;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(lens[i][j]>lens[i][k]+lens[k][j])
lens[i][j]=lens[i][k]+lens[k][j];
int MAX=INF,idx;
for(int i=1;i<=n;i++)
{
int max=0;
for(int j=1;j<=n;j++)
{
if(j==i) continue;
if(lens[j][i]>max) max=lens[j][i]; // 統計每個點的最大需要的長度
}
if(max<MAX) MAX=max,idx=i; // 統計最佳 i 點的在那麼多最大長度中,最小的那一個長度 max
}
if(MAX>=INF) puts("0");
else printf("%d %d\n",idx,MAX);
}
return 0;
}