Submission #3259930

---

Source Code Expand

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int INF = 1000000;
struct bus{int to, cost;};
typedef pair<int, int> P;

int main()
{
  int N, M; cin >> N >> M;
  vector<bus> bs[N+1];
  for (int i = 0; i < M; i++) {
    int from; bus b;
    cin >> from >> b.to >> b.cost;
    bs[from].push_back(b);
    swap(from, b.to);
    bs[from].push_back(b);
  }

  priority_queue<P, vector<P>, greater<P> > que;
  int ans = INF;
  for (int i = 1; i <= N; i++) {
    int d[N+1];
    fill(d, d + N+1, INF);
    d[i] = 0;
    que.push(P(0, i));
    while (!que.empty()) {
      int v = que.top().second, dv = que.top().first;
      que.pop();
      if (d[v] < dv) continue;

      for (int i = 0; i < bs[v].size(); i++) {
        int u = bs[v][i].to, c = bs[v][i].cost;
        if (dv + c < d[u]) {
          d[u] = dv + c;
          que.push(P(d[u], u));
        }
      }
    }

    int tmp = d[1];
    for (int j = 2; j <= N; j++) {
      tmp = max(tmp, d[j]);
    }
    ans = min(tmp, ans);
  }

  cout << ans << endl;
}

Submission Info

Judge Result