Submission #1604309

---

Source Code Expand

#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
typedef pair<int,int> P;

struct Graph{
  Graph(int n):E(n),d(n){};
  vector<vector<P>>E;
  vector<int>d;
  void add_edge(int a,int b,int c){
    E[a].push_back({b,c});
  }
  bool bellmanFord(int s){
    int sz=d.size();
    fill(d.begin(),d.end(),INF);
    d[s]=0;
    for(int i=0;i<sz;++i)
      for(int j=0;j<sz;++j)
        for(P& p:E[j])
          if(d[j]!=INF&&d[j]+p.second<d[p.first]){
            d[p.first]=d[j]+p.second;
            if(i==sz-1)return false;
          }
    return true;
  }
};

main(){
  int n,m,a,b,c,x=1e9;
  cin>>n>>m;
  Graph E(n);
  for(int i=0;i<m;++i){
    cin>>a>>b>>c;
    E.add_edge(--a,--b,c),E.add_edge(b,a,c);
  }
  for(int i=0;i<n;++i){
    E.bellmanFord(i);
    x=min(x,*max_element(E.d.begin(),E.d.end()));
  }
  cout<<x<<endl;
}

Submission Info

Judge Result