Submission #1960080

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cstdio>

using namespace std;

const int NMAX = 300 * 2;

const int TMAX = 300 * 1000 + 1;

array<array<int, NMAX>, NMAX> d;

template<class T> void gc(T &x)
{
    char c;
    int s = 0;
    x = 0;

    c = getchar_unlocked();

    if (c == '-') s = 1;
    else if ('0' <= c && c <= '9')  x = c - '0';

    while (true)
    {
        c = getchar_unlocked();

        if (c < '0' || c > '9') break;
        x = x * 10 + (c - '0');
    }

    if (s) x = -x;
}

int main()
{
    int N, M;

    gc(N);
    gc(M);

    for (int i = 0; i < NMAX; i++)
    {
        d[i].fill(TMAX);
    }

    for (int i = 0; i < M; i++)
    {
        int a, b, t;
        if (scanf("%d%d%d", &a, &b, &t) < 3) return 0;

        // 0-indexed
        a--;
        b--;

        d[a][b] = d[b][a] = t;
    }

    // Warshall–Floyd
    // kは中継点
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    int ans = TMAX;
    for (int i = 0; i < N; i++)
    {
        int mx = -1;
        for (int j = 0; j < N; j++)
        {
            if (i == j) continue;
            mx = max(mx, d[i][j]);
        }
        ans = min(ans, mx);
    }

    printf("%d\n", ans);
    return 0;
}

Submission Info

Judge Result