[플로이드-와샬] 운동(1956)

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

1956번: 운동

 

 

1. 문제 개요

 

1번부터 V번 마을이 있을 때, 시작점으로 돌아오는 사이클 중 가중치 합의 최솟값을 찾는 문제.

 

예를 들어 입력 값이 다음과 같이 주어질때,

 

3 4 //정점수, 간선수1 2 1 3 2 11 3 5 // 1에서 3로 가는 노드의 가중치가 52 3 2

 

2 -> 3 -> 2 3 -> 2 -> 3

 

위와 같이 두 개의 사이클이 만들어질 수 있고 가중치 합의 최소는 3이 된다.

 

 

2. 입출력

 

 

3. 문제 풀이

 

플로이드-와샬 알고리즘으로 모든 쌍 최단 경로를 구한 후 D[i][i] 값 중 최솟값을 출력했다.

경로가 없는 경우에는 INF이 들어가므로 INF 보다 큰 경우에는 -1을 출력했다.

 

 

4. 전체 코드

 

#include <algorithm>
#include <stdio.h>

using namespace std;
//AllPairsShortest
//플로이드 와셜 알고리즘

const int MAX = 401;
const int INF = 10001000;
int D[MAX][MAX]; //최단 경로 값을 저장하는 배열

int main(void)
{
    int n,m; //노드의 수, 간선의 수
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) 
            D[i][j] = INF; //배열 안의 값을 무한대로 초기화
        
    for(int i=0;i<m;i++) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        D[a][b] = c;
    } //a에서 b로 가는 간선의 가중치를 저장한다.
    
    for(int K=1;K<=n;K++) 
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;j++) //K를 경유해 가는 경우가 더 빠르다면 갱신해준다.
                D[i][j] = min(D[i][j], D[i][K] + D[K][j]);
    
    int min = INF;
    for(int i=1;i<=n;i++)
        if(D[i][i] < min) //사이클을 이루는 경로 중 최소값을 찾는다.
            min = D[i][i];
    
    if(min >= INF) printf("-1"); //사이클이 존재하지 않는 경우 -1 출력
    else printf("%d",min);
}