Problem
In the enchanted land of Graph Kingdom, your task is to become a master pathfinder. You must find the shortest route from a starting village to a destination castle, navigating through a network where roads have different lengths. Each road is represented with a weight indicating its length, and your goal is to minimize the travel distance from the start to the destination. This quest involves interpreting graphs with nodes as villages or castles, and edges as roads. The input consists of multiple test cases, each describing a different network of roads. For each test case, determine the shortest path from the given starting point to the destination. Here's what you need to do, step-by-step: 1. Parse the input to understand the number of villages and castles (nodes) and roads (edges) in each test case. 2. Represent the network using a suitable data structure like an adjacency list or matrix. 3. Apply a shortest path algorithm, such as Dijkstra's, to calculate the minimum travel distance. 4. Output the shortest distance for each test case, ensuring to handle cases where no path exists.
- Approach suggestions: Consider using Dijkstra's algorithm for efficient shortest path calculation.
- Algorithm/data structure hints: An adjacency list might be helpful to represent the graph.
- Edge cases to consider: What if there's no path between the start and destination? How will you handle negative weights?
- Optimization tips: Think about how you can minimize the number of nodes you explore, perhaps using priority queues for efficiency.
- Embark on this thrilling journey, and may you become the legendary pathfinder of Graph Kingdom!
Input format
The first line contains two integers, N and M, representing the number of nodes and edges, respectively. The next M lines each contain three space-separated integers, u, v, and w, representing an edge from node u to node v with weight w. The last line contains two integers, S and D, representing the start and destination nodes.
Output format
Output a single integer, the length of the shortest path from node S to node D. If no path exists, output -1.
Constraints
1 <= N <= 1000, 0 <= M <= 5000, 1 <= u, v, S, D <= N, 1 <= w <= 1000
Sample input
5 6 1 2 10 1 3 5 2 3 2 3 2 3 2 4 1 3 4 9 1 4
Sample output
9