[1956] - 운동

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

1956번: 운동

접근 방법

시작점이 주어지지 않았고 종점에서 다시 시작점으로 돌아가야되니 모든 정점에서 최단거리를 찾는 플로이드-워셜 알고리즘을 사용했다.

 

문제 풀이

• 단방향 노선에 최대 정점의 개수가 400, 최대 가중치가 10000이니 inf를 40000001로 설정
• 입력받은 노선을 제외하고 나머지 노선들을 inf로 채우기
• 플로이드-워셜 알고리즘을 사용하여 각 점들에서의 최소값 찾기
• 반복문을 돌며 노선 중 inf가 아닐 때, 출발 i->j 노선과 되돌아가는 j->i 노선(사이클)의 합의 최소값을 ans에 저장
• 만약 ans가 inf면 사이클이 없는것이니 -1, 아니면 사이클이 있으므로 ans 출력

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon.Gold
{
    class _1965
    {
        static int inf = 4000001;
        static void Main(string[] args)
        {
            //0 - 정점, 1 - 간선
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[][] graph = new int[n[0]+1][];
            for (int i = 1; i <= n[0]; i++)
                graph[i] = Enumerable.Repeat(inf, n[0] + 1).ToArray();

            for(int i = 0; i < n[1]; i++)
            {
                int[] m = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph[m[0]][m[1]] = m[2];
            }

            //플로이드 - 워셜
            for(int mid = 1; mid <= n[0]; mid++) //거침
            {
                for(int i = 1; i <= n[0]; i++) //출발
                {
                    for(int j = 1; j <= n[0]; j++) //도착
                        graph[i][j] = Math.Min(graph[i][j], graph[i][mid] + graph[mid][j]);
                }
            }

            int ans = inf;
            for(int i = 1; i <= n[0]; i++)
            {
                for(int j =1; j <= n[0]; j++)   
                {
                    if (i == j)
                        continue;

                    if (graph[i][j] != inf && graph[j][i] != inf)
                        ans = Math.Min(ans, graph[i][j] + graph[j][i]);
                }
            }

            if (ans != inf)
                Console.WriteLine(ans);
            else
                Console.WriteLine(-1);
        }
    }
}