1956번

1956번 - 운동

싸이클을 구하는 문제이다. 

나는 우선 플로이드 워셜 알고리즘을 통해 모든 쌍에 대한 최단거리를 구하였다.

그리고 정점 i 에서 다시 i 로 돌아오는 가장 최단거리는

i 에서 한 정점 k 로 가는 최단거리 + k 에서 다시 i 로 가는 최단거리이기 때문에 이 점을 이용해서 최단거리 싸이클을 구할 수 있었다.

##주의할 점 

- i 에서 i 로 돌아오는 값을 처음에 D[i][i] = 0 이라고 놓으면 , 싸이클을 구할 수 없기 때문에, D[i][i] 는 INF 로 초기화 한다

##다시 깨달은 점

- D[i][i] 를 INF 로 초기화 했기 때문에, 그냥 정답을 D[i][i] 값 중 최소값을 구하면 된다. i 로 돌아오는 싸이클까지 다 계산됨!

<정답 코드>

#include<iostream>
 
using namespace std;
int D[401][401];
const int INF = 987654321;
int main()
{
    int n, e;
    scanf("%d %d", &n, &e);
    
    for (int i = 0; i < 401; i++)
    {
        for (int j = 0; j < 401; j++)
        {
            D[i][j] =INF;
        }
    }
 
    while (e--)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        
        D[a][b] = c;
    }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <=n; i++)
        {
            for (int j = 1; j <=n; j++)
            {
                if (D[i][j] > D[i][k] + D[k][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
 
    int ans = INF;
    for (int i = 1; i <=n; i++)
    {
        for (int j = 1; j <=n; j++)
        {
            long long temp = D[i][j] + D[j][i];
            ans = ans > temp ? temp : ans;
        }
    }
 
    if (ans >= INF)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", ans);
    }
    return 0;
}