Question
Shortest Route to the Last House
You are given a map of a town with n houses connected by m bidirectional roads. Each road has a travel cost associated with it. The houses are numbered from 0 to n − 1.
Your task is to determine the minimum-cost route to travel from House 0 to House n − 1.
Note:
If multiple routes have the same minimum total cost, you may output any one of them.
Input
The first line contains two integers
The following
between houses
n and m representing the number of houses and roads.
The following
m lines each provide three space-separated integers:
u, v, and w, describing a bidirectional road
between houses
u and v with a travel cost of w.Output
Print the shortest path from House 0 to House n-1.
If no such path exists, print
Note:If multiple shortest paths exist, print any one of them.
If no such path exists, print
-1.
Note:If multiple shortest paths exist, print any one of them.
Example
Input:
5 6
0 1 2
0 2 4
1 2 1
1 3 7
2 4 3
3 4 1
Output:
0 1 2 4
Explanation:
You are given a small town map with 5 houses and 6 bidirectional roads (numbered using 0-based indexing).
Your task is to determine the shortest route from House 0 to House 4.
There are several possible routes from House 0 to House 4:
The shortest route is:
5 6
0 1 2
0 2 4
1 2 1
1 3 7
2 4 3
3 4 1
Output:
0 1 2 4
Explanation:
You are given a small town map with 5 houses and 6 bidirectional roads (numbered using 0-based indexing).
Your task is to determine the shortest route from House 0 to House 4.
There are several possible routes from House 0 to House 4:
- 0 → 1 → 2 → 4 with total cost
2 + 1 + 3 = 6 - 0 → 2 → 4 with total cost
4 + 3 = 7 - 0 → 1 → 3 → 4 with total cost
2 + 7 + 1 = 10
The shortest route is:
0 1 2 4with a total cost of 6.