[1238] - 파티

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

1238번: 파티

접근 방법

시작점과 일정한 종점이 주어졌으므로 다익스트라 알고리즘을 사용하였다. 학생마다 집 → 종점 + 종점→ 집의 거리를 구해 가장 오래 걸리는 것이 답.

 

문제 풀이

• 다익스트라를 사용하기위해 리스트로 그래프 만들기
• 우선순위 큐로 (탐색 지점, 가중치)를 넣고, 그래프 내의 현재 탐색 지점에서 갈 수 있는 곳의 가중치를 비교 후, 최솟값으로 다시 큐에 넣어주기
• 1번 학생부터 N번 학생까지 반복문으로 다익스트라를 사용하여 집 → X, X → 집의 거리를 구한 뒤 합, 학생중 최대값을 ans 에 저장
• ans 출력

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

namespace Baekjoon.Gold
{
    class _1238
    {
        static List<(int, int)>[] graph;
        static int v;

        static void Main(string[] args)
        {
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            v = n[0];
            int x = n[2];

            graph = new List<(int, int)>[v + 1];
            for (int i = 1; i <= v; i++)
                graph[i] = new List<(int, int)>();

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


            int ans = 0;
            for(int i = 1; i<= v; i++)
            {
                int go = dijkstra(i, x);
                int back = dijkstra(x, i);

                ans = Math.Max(ans, go + back);
            }

            Console.WriteLine(ans);

        }

        static int dijkstra(int start, int end)
        {
            bool[] visited = new bool[v + 1];

            int[] distance = Enumerable.Repeat(1000001, v + 1).ToArray();
            PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
            pq.Enqueue(start, 0);
            distance[start] = 0;

            while (pq.Count > 0)
            {
                int point = pq.Dequeue();

                if (!visited[point])
                {
                    visited[point] = true;

                    foreach ((int, int) next in graph[point])
                    {
                        distance[next.Item1] = Math.Min(distance[next.Item1], distance[point] + next.Item2);
                        pq.Enqueue(next.Item1, distance[next.Item1]);
                    }
                }
            }

            return distance[end];
        }
    }
}