[백준 1956] 운동

문제 출처: https://www.acmicpc.net/problem/1956

풀이

사소한 오타 하나때문에 15번정도 제출오류가 났던 문제입니다.

풀이 방법순으로 적어보면,

1. map을 INF로 초기화해놓는다.

2. 플로이드와샬을 돌려서 map에 각 노드에서 각 노드로 가는 최단거리를 저장한다.

3. 각 노드에서 노드로 가는 길 중 INF가 아닐때만(길이 있을 때만) 사이클의 최단길이를 비교합니다.

4. map[i][j]!=INF&&map[j][i]!=INF이면 사이클이 존재하는 것이고, 결국 temp가 INF라면 사이클이없으므로, -1을출력합니다. 

코드

#include<iostream>
#include<algorithm>
using namespace std;
int INF = 4000000;
int map[400][400];
int main()
{
    int v, e, a, b, c;
    cin >> v >> e;
    for (int i = 0; i < 400; i++)
    {
        for (int j = 0; j < 400; j++)
        {
            map[i][j] = INF;
        }
    }
    for (int i = 0; i < e; i++)
    {
        cin >> a >>b>> c;
        map[a- 1][b - 1] = c;
    }
    for (int k = 0; k < v; k++)
    {
        for (int i = 0; i < v; i++)
        {
            for (int j = 0; j < v; j++)
            {
                if (map[i][j] > map[i][k] + map[k][j])
                    map[i][j] = map[i][k] + map[k][j];
            }
        }
    }
    int temp = INF;
    for (int i = 0; i < v; i++)
    {
        for (int j = 0; j < v; j++)
        {
            if (i == j)
                continue;
            if (map[i][j] != INF && map[j][i] != INF)
            {
                temp = min(temp, map[i][j] + map[j][i]);
            }
        }
    }
    if (temp == INF)cout << -1 << endl;
    else cout << temp;
}

결과