Submission #1772193

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FAST cin.tie(0),ios::sync_with_stdio(false)
#define pb push_back
#define mkp make_pair
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)

#define fi first
#define se second
#define debug(x) cerr << #x << ':' << x << endl;
typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
typedef vector<Pii> Vp;

inline int chmin(int &a, int b){return b<a? a=b,1 : 0;}

const int INF = 1 << 29;

int n,m;
Vp node[302];
int mcost[302];
int dijkstra(int p);

main(){
  FAST;
  cin >> n >> m;
  rep(i,m){
    int a,b,c;
    cin >> a >> b >> c;
    node[a].pb(mkp(c,b));
    node[b].pb(mkp(c,a));
  }

  int ans = INF;
  reps(i,1,n){
    chmin(ans,dijkstra(i));
  }
  cout << ans << endl;
}

int dijkstra(int p){
  priority_queue< Pii, Vp, greater<Pii> > pq;
  reps(i,1,n)mcost[i] = INF;
  pq.push(mkp(0,p));
  mcost[p] = 0;

  while(!pq.empty()){
    Pii now = pq.top();pq.pop();
    int pos = now.se;
    int cost = now.fi;
    rep(i, node[pos].size()){
      int ncost = node[pos][i].fi;
      int nxt = node[pos][i].se;
      if( chmin(mcost[nxt], cost+ncost))
        pq.push(mkp(cost+ncost, nxt));
    }
  }
  //reps(i,1,n)cerr << p << "mcost["<<  i << "]:" << mcost[i] << endl;
  return *max_element(mcost+1, mcost+n+1);
}

Submission Info

Judge Result