[BOJ/백준] 1956 - 운동

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

1956번: 운동

각 정점은 일방향 가중치가 존재하는 간선으로 연결 되어 있으며 이들 사이를 움직이는 가중치의 합이 최소인 사이클을 찾는 알고리즘을 설계해야 한다.

​

처음에는 각 정점에서 출발하여서 모든 가능한 모든 경로를 재귀함수로 돌게 하는 코드를 짜 보았으나 실패하였다.

​

이 문제는 플로이드-워셜 알고리즘을 이용해 간단하게 해결할 수 있다.

#include<iostream>
#include<algorithm>
#define M 1<<20
using namespace std;

int v,e[401][401],res=M;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(NULL);

    cin >> v;
    int roads;
    cin >> roads;
    for(int i=1; i<=v; i++){
        for(int j=1; j<=v; j++){
            e[i][j] = M;
        }
    }
    for(int i=0; i<roads; i++){
        int a,b,c;
        cin >> a >> b >> c;
        e[a][b] = c;
    }
    
    for(int k=1; k<=v; k++){
        for(int i=1; i<=v; i++){
            for(int j=1; j<=v; j++){
                if(e[i][k] + e[k][j] < e[i][j]){
                    e[i][j] = e[i][k] + e[k][j];
                }
            }
        }
    }

     for(int i=1; i<=v; i++){
        for(int j=1; j<=v; j++){
            if(i == j) continue;
            res = min(res, e[i][j]+e[j][i]);
        }
    }
    
    res = res==M ? -1 : res;
    cout << res;
    return 0;
}
[출처] [BOJ/백준] 1956 - 운동|작성자 윤댕