Advanced Computer Networks(CEG-7450-01) - Packet Routing: Part I. Least Cost Path Routing (Java Solution) Packets in a network need to traverse a minimum-cost route. Design an algorithm to determine which nodes the packets will definitely visit if least cost path(s) are used. Note there may be multiple least cost paths.
INPUT FORMAT:
Unlike previous labs, this lab reads input from the standard input. DO NOT include any package statement in your program.
The first input line contains two integers n (1<= n <= 10^5) and m (1<=m<=2x10^5): the number of nodes and the number of links. The nodes are numbered 1,2,…,n. Node 1 is the source, and node n is the destination.
After this first line, there are m lines describing the links. Each line has three integers a, b, and c: there is a link from node a to node b with cost c. All links are directional. That is, a, b, c indicates that there is a link from a to b only, with a cost of c. In addition, 1 <=a, b<=n, 1<=c <=10^9.
You may assume that there is a route from the source to the destination.
OUTPUT FORMAT:
Unlike previous labs, the output is to the standard output.
First print an integer k: the number of nodes that are certainly in the route. After this, print the k nodes sorted in increasing order.
SAMPLE INPUT 1:
5 6
1 2 3
1 3 4
2 3 1
2 4 5
3 4 1
4 5 8
SAMPLE OUTPUT 1:
4
1 3 4 5
For Assignment Help Please WhatsApp at:
+91-995 3141 035
Solution Includes: AI writing Detection and Plagiarism report with 100% Accuracy.
