5.6 🗺️🚴♂️Dhrumil's City Bike Quest 🏙️🚲
There are n cities in your country, numbered from 1 to n
You are currently on city 1 and want to reach city n
Each city has a bike which has a weight of x[i] kg
Lets say the distance between 2 nodes is 5, then you will require 5 * x[i] seconds to travel.
You can choose to either continue with a bike u already have, or choose a new bike from the city.
You are given m edges, bidirectional roads
Find the minimum time to reach nth city
Constraints
All values are Integers(10^9)
Input Format
First Line: An integer T representing the number of test cases.
For Each Test Case:
First Line: Three integers n (number of cities), m (number of bidirectional roads), and b (maximum weight of a bike).
Second Line: An array of n integers x[i] representing the weights of bikes in each city.
Next m Lines: Each line contains three integers representing a road between source(u) and destination(v) with distance d.
Output Format
The output numbers correspond to the minimum time taken to reach city n from source city in each test case.
Example 1
Input:
1
5 5
1 2 2
3 2 1
2 4 5
2 5 7
4 5 1
5 2 1 3 3
Output:
19
Explanation:
n=5, m=5
Edge from 1->2 distance = 2
Edge from 3->2 distance = 1
Edge from 2->4 distance = 5
Edge from 2->5 distance = 7
Edge from 4->5 distance = 1
The bike weights of each node respectively are 5, 2, 1, 3, 3
The optimal way is go from 1 to 2 with bike 1 => 10s time
Then take bike 2 with weight = 2, then go from 2 to 3 => 2s time
Then take bike 3 with weight = 1, then go from 3 to 2 => 1s time
Now go from 2 to 4 with the same bike => 5s time
Then go to 4 to 5 => 1s time
Total = 19s time
Log In to solve the Question