[백준 1956] 운동

최단거리 + 사이클 문제라 사이클이라는 단어에 꽂혀서 방향을 잡는데 조금 시간이 걸렸다.

 

하지만 이 문제는 사이클을 구성하는 노드에 관한 문제도 아니고 그냥 사이클의 존재 유무에 대한 문제이다.

 

그리고 사이클의 거리는 A → B 거리 + B → A 거리로 표현할 수 있다.

 

 따라서 플로이드워셜로 돌린 후 dist[A][B] 와 dist[B][A] 값이 유효할 경우 dist[A][B] + dist[B][A] 값을 구해서 계속 최신화하면 된다.

 

플로이드워셜로 모든 정점에서 모든 정점까지의 최단거리를 구한 후

dist[A][B] + dist[B][A] 를 통해 사이클에 대한 최단거리를 구할 수 있다는 것이다.

---

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

using namespace std;

#define SIZE 401
#define INF int(1e9)

int V, E;
int dp[SIZE][SIZE];

void solve()
{
    // 플로이드 워셜로 모든 정점에서 모든 정점까지의 최단거리 구하기
    for (int mid = 1; mid <= V; mid++)
    {
        for (int start = 1; start <= V; start++)
        {
            // start에서 mid로 갈 수 없으면 스킵
            if (start == mid || dp[start][mid] == INF)
            {
                continue;
            }

            for (int end = 1; end <= V; end++)
            {
                // mid에서 end로 갈 수 없으면 스킵
                if (end == mid || dp[mid][end] == INF)
                {
                    continue;
                }

                // start에서 end로 갈 수 있는거리 최신화
                dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid][end]);
            }
        }
    }

    // for (int i = 1; i <= V; i++)
    // {
    //     for (int k = 1; k <= V; k++)
    //     {
    //         cout << dp[i][k] << " ";
    //     }
    //     cout << "\n";
    // }

    int ans = INF;
    for (int i = 1; i <= V; i++)
    {
        for (int k = i + 1; k <= V; k++)
        {
            if (dp[i][k] != INF && dp[k][i] != INF)
            {
                ans = min(ans, dp[i][k] + dp[k][i]);
            }
        }
    }

    if (ans == INF)
    {
        cout << "-1";
    }
    else
    {
        cout << ans;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> V >> E;

    for (int i = 1; i <= V; i++)
    {
        for (int k = 1; k <= V; k++)
        {
            dp[i][k] = INF;
        }
    }

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

    // 자기 자신으로의 경로는 0
    for (int i = 1; i <= V; i++)
    {
        dp[i][i] = 0;
    }

    solve();

    return 0;
}