Submission #2861137

---

Source Code Expand

#include <stdio.h>

#define MAX_INT (-1U>>1)
#define MAX(x, y) ((x)>(y)?(x):(y))
#define MIN(x, y) ((x)>(y)?(y):(x))

int n, m;
int bus[300][300];
int visited[300];

int ge(int from, int to) {
    visited[from] = 1;
    if (bus[from][to] != MAX_INT) return bus[from][to];
    int min = MAX_INT;
    for (int i = 0; i < n; i++) {
        if (visited[i] || bus[from][i] == MAX_INT) continue;
        min = MIN(min, bus[from][i] + ge(i, to));
    }
    bus[from][to] = min;
    bus[to][from] = min;
    return min;
}

int main() {
    int a, b, i, j, k, t, min = MAX_INT, res[300], tmp;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) bus[i][j] = MAX_INT;
        bus[i][i] = 0;
    }
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &t);
        bus[a - 1][b - 1] = t;
        bus[b - 1][a - 1] = t;
    }
    for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
        ge(i, j);
        for(k = 0; k < n; k++) visited[k] = 0;
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) tmp = MAX(tmp, bus[i][j]);
        min = MIN(tmp, min);
        tmp = 0;
    }
    printf("%d\n", min);
    return 0;
}

Submission Info

Judge Result