[C#] 1753번 최단경로

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

 

코드

using System;
using System.Collections.Generic;

class Dijkstra
{
    static int INF = int.MaxValue;

    static void Main()
    {
        string[] firstLine = Console.ReadLine().Split();
        int V = int.Parse(firstLine[0]);
        int E = int.Parse(firstLine[1]);

        int K = int.Parse(Console.ReadLine());

        List<(int, int)>[] 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 < E; i++)
        {
            string[] edge = Console.ReadLine().Split();
            int u = int.Parse(edge[0]);
            int v = int.Parse(edge[1]);
            int w = int.Parse(edge[2]);

            graph[u].Add((v, w));
        }

        int[] distances = DijkstraAlgorithm(graph, V, K);

        for (int i = 1; i <= V; i++)
        {
            Console.WriteLine(distances[i] == INF ? "INF" : distances[i].ToString());
        }
    }

    static int[] DijkstraAlgorithm(List<(int, int)>[] graph, int V, int start)
    {
        int[] distances = new int[V + 1];
        for (int i = 1; i <= V; i++)
        {
            distances[i] = INF;
        }
        distances[start] = 0;

        SortedSet<(int, int)> pq = new SortedSet<(int, int)>();
        pq.Add((0, start)); 

        while (pq.Count > 0)
        {
            var current = pq.Min;
            pq.Remove(current);
            int currentDistance = current.Item1;
            int currentNode = current.Item2;

            if (currentDistance > distances[currentNode]) continue;

            foreach (var neighbor in graph[currentNode])
            {
                int nextNode = neighbor.Item1;
                int weight = neighbor.Item2;

                int newDistance = currentDistance + weight;

                if (newDistance < distances[nextNode])
                {
                    pq.Remove((distances[nextNode], nextNode));

                    distances[nextNode] = newDistance;
                    pq.Add((newDistance, nextNode));
                }
            }
        }
        return distances;
    }
}

 

 

실행화면

 

 

---

문제링크: https://www.acmicpc.net/problem/1753