C# 백준 1504 특정한 최단 경로

특정한 최단 경로

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

84123

22484

15236

25.000%

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

 

 

 

https://blog.naver.com/ambidext/221285681447

[C#] Priority Queue (우선순위 큐)

 

우선순위 큐 소스

 

이 문제는 다익스트라로 구현을 하는 문제이지만 특별한 조건이 있다. 아래쪽에 있는 마지막 입력 줄에 있는 특정 노드들은 무조건 거치고 최단경로를 구해야 하고 모든 노드들을 거쳐야 한다는 것 모든 노드들을 지나가지 못했거나 특정 두 노드들이 이어지지 않았다면 -1을 출력

 

결론은 바로 최단 경로를 구하는것이 아닌 특정 노드들을 거친 노드를 더 해서 가야되는것이다.

 

특정 노드들을 v1 v2로 칭하고

 

이 특정 노드를 지나가는 방법은 2가지가 있는데

 

첫번째는 시작 노드에서 v1의 최단경로를 구하고 v2를 지나서 n번 노드의 최단경로를 구하는것과

두번쨰는 시작 노드에서 v2의 최단경로를 구하고 v1을 지나서 n번 노드의 최단경로를 구하는것

 

이 조건을 맞춰서 구할려면

 

먼저 v1 v2의 최단경로를 구하고

 

현재 시작정점에서 v1까지의 최단경로 + v1 v2 최단경로 + v2에서 n번 노드의 최단경로를 구하고

현재 시작정점에서 v2까지의 최단경로 + v2 v1 최단경로 + v1에서 n번 노드의 최단경로를 구해서

 

둘을 서로 비교해서 가장 낮은 최단경로를 출력하면 되는거다.

 

서로 INF를 넘어서면 -1을 출력

 

내가 푼 코드

    class Program
    {
        static int n;
        static int m;
        static int INF = 100000000;
        static int[] d;
        static List<(int weight, int node)>[] maps;
        static void Main(string[] args)
        {
            string[] arr = Console.ReadLine().Split();

            n = int.Parse(arr[0]);
            m = int.Parse(arr[1]);


            maps = new List<(int weight, int node)>[n + 1];

            for (int i = 1; i < n + 1; i++)
            {
                maps[i] = new List<(int weight, int node)>();
            }

            for (int i = 0; i < m; i++)
            {
                arr = Console.ReadLine().Split();

                int v = int.Parse(arr[0]);
                int e = int.Parse(arr[1]);
                int w = int.Parse(arr[2]);

                maps[v].Add((w, e));
                maps[e].Add((w, v));
            }

            arr = Console.ReadLine().Split();

            int v1 = int.Parse(arr[0]);
            int v2 = int.Parse(arr[1]);

            int V1V2 = Dijkstra(v1, v2);
            int V2V1 = Dijkstra(v2, v1);

            int v1v2 = Dijkstra(1, v1) + V1V2 + Dijkstra(v2, n);
            int v2v1 = Dijkstra(1, v2) + V2V1 + Dijkstra(v1, n);

            int result = v1v2 < v2v1 ? v1v2 : v2v1;

            if (result >= INF)
            {
                Console.WriteLine(-1);
            }
            else
            {
                Console.WriteLine(result);
            }

        }

        static int Dijkstra(int start, int end)
        {
            d = new int[n + 1];

            for (int i =1; i < d.Length; i++)
            {
                d[i] = INF;
            }

            d[start] = 0;

            MinHeap<Tuple<int, int>> pq = new MinHeap<Tuple<int, int>>();

            pq.Add(new Tuple<int, int>(d[start], start));

            while (pq.Count != 0)
            {
                int distance = pq.GetMin().Item1;
                int current = pq.ExtractDominating().Item2;

                if (d[current] < distance) continue;

                for (int i = 0; i < maps[current].Count; i++)
                {
                    int node = maps[current][i].node;
                    int weight = distance + maps[current][i].weight;

                    if (d[node] > weight)
                    {
                        d[node] = weight;

                        pq.Add(new Tuple<int, int>(d[node], node));
                    }
                }
            }
           
            return d[end];
        }
    }
}