백준 1956 운동 - 플로이드-와샬, C++

1956번: 운동

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 999999999
using namespace std;

int v, e;
int a, b, c;
int road[401][401];
int res = MAX;

void Floyd(){
    for(int via = 1; via <= v; via++){
        for(int from = 1; from <= v; from++){
            if(road[from][via] == MAX)
                continue;

            for(int to = 1; to <= v; to++){
                if(road[via][to] == MAX)
                    continue;
                
                if(road[from][to] > road[from][via] + road[via][to])
                    road[from][to] = road[from][via] + road[via][to];
            }
        }
    }
}

int main(){
    for(int i = 0; i <= 400; i++){
        for(int j = 0; j <= 400; j++){
            road[i][j] = MAX;
        }
    }

    scanf("%d %d", &v, &e);

    while (e--){
        scanf("%d %d %d", &a, &b, &c);
        road[a][b] = c;
    }

    Floyd();

    for(int i = 1; i <= v; i++){
        for(int j = 1; j <= v; j++){
            if(i == j)
                continue;

            if(road[i][j] != MAX && road[j][i] != MAX)
                res = min(res, road[i][j] + road[j][i]);
        }
    }

    if(res == MAX)
        printf("-1\n");
    else
        printf("%d", res);
}

---

 플로이드-와샬을 한 후 사이클이 있는걸 판단하는 문제입니다. 단순 플로이드 알고리즘들과 같은 랭크라 큰 어려움은 없는 문제입니다. 사이클을 판단하는 기준은 'a->b 경로가 있고 b-> a 경로가 있는 경우'이며 위 코드에서는

            if(road[i][j] != MAX && road[j][i] != MAX)
                res = min(res, road[i][j] + road[j][i]);

이 부분이 해당이 됩니다. 혹시 사이클이 있다면 res에 최소 사이클을 넣어줌으로서 답을 찾아낼 수 있습니다.