[C++][백준 1956] 운동

[문제]

1956번: 운동 (acmicpc.net)

1956번: 운동

---

[문제 풀이]

플로이드 워셜을 이용해서 풀도록 하자.

플로이드 워셜 알고리즘을 사용한 뒤에 행렬에서 [i][i]가 존재한다면 자기 자신으로 돌아오는 사이클이 있다는 의미이므로 i,i 를 모두 확인해 준 뒤 min값을 꺼내자.

*주의 사항 : 만약 사이클이 없다면 -1을 출력하자.

*주의 사항2 : 거리는 10,000 이하이고 마을은 400까지 있으니 4,000,000 까지 갈 수가 있다. 그러니 INF 값을 4,000,000 이상의 값으로 하지 않으면 오류가 발생한다.

---

[코드]

#include<iostream>
#include<algorithm>
#include <vector>

using namespace std;

const int INF = 10000000;
int v,e;
int country[401][401];

void output(){
    cout<<"----output-----"<<endl;
    for(int i = 1;i<=v;i++){
        for(int j = 1;j<=v;j++){
            cout<<country[i][j]<<" ";
        }
        cout<<endl;
    }
    return;
}

void floid(){
    for(int k = 1;k<=v;k++){
        for(int i = 1;i<=v;i++){
            for(int j = 1;j<=v;j++){
                if(country[i][j] > country[i][k] + country[k][j]){
                    country[i][j] = country[i][k] + country[k][j];
                }
            }
        }
    }
    return;
}

void solve(){
    floid();
    int answer = INF;
    for(int i = 1;i<=v;i++){
        if(answer > country[i][i]){
            answer = country[i][i];
        }
    }

    cout<< ((answer == INF) ? -1 :answer )<<endl;
    
    return;
}

int main(){
    cin>>v>>e;
    for(int i = 0;i<=v;i++){
        fill(country[i],country[i]+v + 1,INF);
    }

    for(int i = 0;i<e;i++){
        int a,b,c;
        cin>>a>>b;
        cin>>c;
        country[a][b] = c;
    }

    solve();

    return 0;
}