Submission #4193226

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;
int d[303][303];

signed main(){
  int N,M;cin>>N>>M;
  const int INF=1e9+7;
  for(int i=0;i<N;i++)for(int j=0;j<N;j++)d[i][j]=INF;
  for(int i=0;i<N;i++)d[i][i]=0;
  for(int i=0;i<M;i++){
    int a,b,t;
    cin>>a>>b>>t;a--;b--;
    d[a][b]=t;d[b][a]=t;
  }
  for(int k=0;k<N;k++){
    for(int j=0;j<N;j++){
      for(int i=0;i<N;i++){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }
  //cout<<d[0][1]<<" "<<d[0][2]<<" "<<d[1][2]<<endl;
  int fans=INF;
  for(int i=0;i<N;i++){
    int ans=0;
    for(int j=0;j<N;j++)ans=max(ans,d[i][j]);
    fans=min(fans,ans);
  }
  cout<<fans<<endl;
}

Submission Info

Judge Result