\n \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc77c\ubc18\uc801\uc778 \ucd5c\ub2e8 \uacbd\ub85c \uc54c\uace0\ub9ac\uc998(\ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998, \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998 \ub4f1)\uc740 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ud55c \uac00\uc9c0\ub9cc \ucc3e\uc9c0\ub9cc, \uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \uc8fc\uc5b4\uc9c4 \ub450 \uc815\uc810 \uc0ac\uc774\uc758 K\ubc88\uc9f8\ub85c \uc9e7\uc740 \uacbd\ub85c\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n
\n\uc785\ub825 \ud615\uc2dd:<\/strong>\n<\/p>\n \n\ucd9c\ub825 \ud615\uc2dd:<\/strong>\n<\/p>\n \n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc0ac\uc6a9\ub418\ub294 \uc54c\uace0\ub9ac\uc998\uc740 \uc6b0\uc120\uc21c\uc704 \ud050\ub97c \ud65c\uc6a9\ud55c \uadf8\ub798\ud504 \ud0d0\uc0c9\uc785\ub2c8\ub2e4. \uc804\ud1b5\uc801\uc778 \ucd5c\ub2e8 \uacbd\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \ubcc0\ud615\ud558\uc5ec K\ubc88\uc9f8\ub85c \uc9e7\uc740 \uacbd\ub85c\ub97c \ucc3e\ub294 \uc811\uadfc \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud569\ub2c8\ub2e4. \ud2b9\ud788, \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uacfc \uc6b0\uc120\uc21c\uc704 \ud050\uc758 \uc870\ud569\uc73c\ub85c \ud544\uc694\ud55c \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uacfc\uc815\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:\n <\/p>\n \n \uc544\ub798\ub294 \uc704\uc758 \uacfc\uc815\uc744 C#\uc73c\ub85c \uad6c\ud604\ud55c \ucf54\ub4dc\uc785\ub2c8\ub2e4.\n <\/p>\n \n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O((M + N) log N) \uc785\ub2c8\ub2e4. \uc774\uc720\ub294:\n <\/p>\n \n \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uadf8\ub798\ud504 \ud0d0\uc0c9\uc5d0 \ub300\ud55c \uae30\ubcf8 \uac1c\ub150\uc744 \ubc14\ud0d5\uc73c\ub85c \ucf54\ub4dc\ub97c \uad6c\ud604\ud588\uc2b5\ub2c8\ub2e4. \ucd5c\ub2e8 \uacbd\ub85c \uc811\uadfc\ubc95\uc744 \ubcc0\ud615\ud574\uc11c K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubc29\ubc95\uc744 \ud559\uc2b5\ud558\uba74\uc11c, \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c\uc758 \uc804\ub7b5\uc801 \uc0ac\uace0\ub97c \ud0a4\uc6b8 \uc218 \uc788\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4.\n <\/p>\n \n \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \uc880 \ub354 \ubcf5\uc7a1\ud55c \uadf8\ub798\ud504 \ud0d0\uc0c9 \ubb38\uc81c\ub97c \ub2e4\ub8e8\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4. \ucd94\uac00\uc801\uc73c\ub85c \uad81\uae08\ud55c \uc810\uc774\ub098 \ud53c\ub4dc\ubc31\uc774 \uc788\ub2e4\uba74 \ub313\uae00\ub85c \ub0a8\uaca8 \uc8fc\uc138\uc694!\n <\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\n
\n
\uc608\uc81c<\/h2>\n
\n \uc785\ub825: \n 4 5 2\n 1 2 1\n 1 3 2\n 2 3 1\n 2 4 3\n 3 4 1\n\n \ucd9c\ub825:\n 3\n <\/pre>\n
\ubb38\uc81c \ubd84\uc11d<\/h2>\n
\n
C# \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n
\n using System;\n using System.Collections.Generic;\n\n class Program\n {\n static void Main(string[] args)\n {\n \/\/ \uc785\ub825 \ubc1b\uae30\n var line = Console.ReadLine().Split();\n int N = int.Parse(line[0]); \/\/ \uc815\uc810 \uc218\n int M = int.Parse(line[1]); \/\/ \uac04\uc120 \uc218\n int K = int.Parse(line[2]); \/\/ K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\n\n \/\/ \uadf8\ub798\ud504 \ucd08\uae30\ud654\n var graph = new List<(int to, int cost)>[N + 1];\n for (int i = 0; i <= N; i++)\n {\n graph[i] = new List<(int, int)>();\n }\n\n \/\/ \uac04\uc120 \uc815\ubcf4 \uc785\ub825\n for (int i = 0; i < M; i++)\n {\n line = Console.ReadLine().Split();\n int a = int.Parse(line[0]);\n int b = int.Parse(line[1]);\n int cost = int.Parse(line[2]);\n graph[a].Add((b, cost));\n }\n\n \/\/ K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c \ucc3e\uae30\n var result = FindKthShortestPath(graph, N, K);\n Console.WriteLine(result);\n }\n\n static int FindKthShortestPath(List<(int to, int cost)>[] graph, int N, int K)\n {\n var pq = new SortedSet<(int cost, int node, int count)>();\n pq.Add((0, 1, 0)); \/\/ (cost, node, count)\n\n \/\/ K\ubc88\uc9f8 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uc704\ud55c \ub9ac\uc2a4\ud2b8\n var paths = new List\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n
\uacb0\ub860<\/h2>\n