BOJ 1956 : 운동

문제링크

풀이요약

플로이드 워셜

풀이상세

1. 플로이드 워셜을 통해, 전 범위의 최단거리를 구한다. 단 다른 노드를 거쳐가는 과정을 통해 자신의 자리로 돌아올 수 있다면 즉, 동일한 인덱스의 경우 0 이 아닌 값이 저장되어 있다면 그 값이 사이클을 통해 돌아온 값이 된다.

2. 해당 배열의 경우 0으로 초기화 되어있는 상태이므로, 반드시 0이 아닌 값끼리 더해주도록 조건을 세웠다.

#include<iostream>
using namespace std;
int N, M, a[404][404], INF = 987654321;
void input(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> M;
    int st,ed,dist;

    for(int i=0; i<M; i++) {
        cin >> st >> ed >> dist;
        a[st][ed] = dist;
    }
}

void solve() {
    for(int k=1; k<=N; k++) {
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(a[i][k] && a[k][j]) {
                    a[i][j] = a[i][j] == 0 ? a[i][k]+a[k][j] : min(a[i][j],a[i][k]+a[k][j]);
                }
            }
        }
    }
}

void output() {
    int ans = INF;
    for(int i=1; i<=N; i++) {
        if(a[i][i]) ans = min(a[i][i], ans);
    }
    cout << (ans == INF ? -1 : ans);
}
int main() {
    input();
    solve();
    output();
}