Submission #1367876

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin(); it!=(c).end(); it++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define pr(a) cout << (a) << endl
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> P;
const int MAX=2000000001;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
 
int main() {
  int d[301][301];
  memset(d,MAX,sizeof(d));
  rep(i,301) d[i][i]=0;
  int n,m;
  cin >> n >> m;
  rep(i,m) {
    int x,y,z;
    cin >> x >> y >> z;
    x--;
    y--;
    d[x][y]=z;
    d[y][x]=z;
  }
  rep(k,n) {
    rep(i,n) {
      rep(j,n) if(d[i][k]!=MAX && d[k][j]!=MAX) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
  }
  int ans=0,Min=MAX;
  rep(i,n) {
    int Max=0;
    rep(j,n) Max=max(Max,d[i][j]);
    if(Max<Min) {
      ans=i+1;
      Min=Max;
    }
  }
  pr(Min);
  return 0;
}

Submission Info

Judge Result