1956번: 운동

https://www.acmicpc.net/problem/1956


$O(v^3)$

초기에 i->i 가는 비용을 무한대로 설정하고 플로이드 알고리즘을 돌려본다.
이후 i->i 가는 비용의 최솟값을 출력한다. 이 값이 무한대이면 사이클은 존재하지 않는다.

#include<cstdio>
int v, e, dis[401][401], mini = 1e9, x, y, z;
int main() {
    scanf("%d%d", &v, &e);
    for (int i = 1; i <= v; i++)
        for (int j = 1; j <= v; j++) dis[i][j] = 1e9;
    while (e--) scanf("%d%d%d", &x, &y, &z), dis[x][y] = z;
    for (int k = 1; k <= v; k++) for (int i = 1; i <= v; i++) for (int j = 1; j <= v; j++)
        if (dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j];
    for (int i = 1; i <= v; i++) if (mini > dis[i][i]) mini = dis[i][i];
    printf("%d", mini < 1e9 ? mini : -1);
    return 0;
}