\n This is a problem of finding the K-th shortest path between two given vertices in a graph. Common shortest path algorithms (such as Dijkstra’s algorithm, Bellman-Ford algorithm, etc.) find only one shortest path, but in this problem, we need to find the K-th shortest path between the given two vertices.\n <\/p>\n
\nInput Format:<\/strong>\n<\/p>\n \nOutput Format:<\/strong>\n<\/p>\n \n The algorithm used to solve this problem is a graph search utilizing a priority queue. It employs a modified approach to traditional shortest path algorithms to find the K-th shortest path. In particular, it explores the necessary paths using a combination of Dijkstra’s algorithm and a priority queue.\n <\/p>\n \n The process to solve the problem is as follows:\n <\/p>\n \n Below is the code implementing the above process in C#.\n <\/p>\n \n The time complexity of this algorithm is O((M + N) log N). The reasons are:\n <\/p>\n\n
\n
Example<\/h2>\n
\n Input: \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 Output:\n 3\n <\/pre>\n
Problem Analysis<\/h2>\n
\n
C# Code Implementation<\/h2>\n
\n
\n using System;\n using System.Collections.Generic;\n\n class Program\n {\n static void Main(string[] args)\n {\n \/\/ Input\n var line = Console.ReadLine().Split();\n int N = int.Parse(line[0]); \/\/ Number of vertices\n int M = int.Parse(line[1]); \/\/ Number of edges\n int K = int.Parse(line[2]); \/\/ K-th shortest path\n\n \/\/ Initialize the graph\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 \/\/ Input edge information\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 \/\/ Find the K-th shortest path\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 \/\/ List for the K-th shortest path\n var paths = new ListTime Complexity Analysis<\/h2>\n