Submission #3994873

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://atcoder.jp/contests/abc012/tasks/abc012_4

int N, M;
struct Edge
{
    int to;
    int cost;
};
vector<Edge>G[333];

int dijkstra(int s) {
    int dst[N];
    fill(dst, dst + N, INF);
    min_priority_queue<P> q;
    q.push({0, s});
    dst[s] = 0;

    while(!q.empty()) {
        P p = q.top(); q.pop();
        int v = p.second;

        if (dst[v] < p.first) {
            continue;
        }

        for (Edge e : G[v]) {
            if (dst[e.to] > dst[v] + e.cost) {
                dst[e.to] = dst[v] + e.cost;
                q.push({dst[e.to], e.to});
            }
        }
    }

    int max = 0;
    REP(i, N) {
        max = std::max(max, dst[i]);
    }
    return max;
}

int main() {
    cin >> N >> M;
    int a, b, t;
    REP(i, M) {
        cin >> a >> b >> t;
        a--; b--;
        G[a].push_back({b, t});
        G[b].push_back({a, t});
    }

    int min = INF;
    REP(i, N) {
        min = std::min(min, dijkstra(i));
    }
    cout << min << "\n";

    return 0;
}

Submission Info

Judge Result