[1956] 운동

[2021.03.09]

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int mat[405][405] = {};
    int V, E, INF = 100000000, answer = INF;

    scanf("%d %d", &V, &E);
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (i == j) continue;
            mat[i][j] = INF;
        }
    }
    while (E--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        mat[a - 1][b - 1] = c;
    }
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
            }
        }
    }
    for (int i = 0; i < V; i++) {
        for (int j = i + 1; j < V; j++) {
            if (i == j) continue;
            answer = min(answer, mat[i][j] + mat[j][i]);
        }
    }
    (answer == INF) ? printf("-1") : printf("%d", answer);
}