Drive
Time limit2sMemory limit128 MB
Find a path from S to T in a weighted undirected graph minimizing extra cost incurred whenever an edge's weight falls outside the running min-max range of used edges.
- Level
Hard8 of 10
- Topics
- Shortest path, Graph, Binary search, Dynamic programming
- Solved
- No attempts yet
Problem
There is a country with n cities. The cities are numbered from 1 to n, and some pairs of cities are connected by roads. You are currently in city S and want to drive to city T.
Each road has a cost. After the drive begins, you pay nothing for the first road you use. For every later road, let m be the minimum road cost among the roads used so far, M be the maximum road cost among the roads used so far, and x be the cost of the road you are about to use.
- If
x < m, you additionally paym - x. - If
x > M, you additionally payx - M. - If
m <= x <= M, you pay nothing extra.
For example, if you use roads with costs 3, 1, 5, 4, 2, 7 in that order, the payments for those roads are 0, 2, 2, 0, 0, 2, for a total payment of 6.
Given the road information, find a driving route whose total payment is minimum.
Input
The first line contains four integers n, m, S, and T. Here, n is the number of cities and m is the number of roads.
3 <= n <= 5001 <= m <= 2,000
Each of the next m lines contains three integers a, b, and c, describing one road. It means that the road connecting cities a and b has cost c.
1 <= c <= 1,000,000,000aandbare different.- At most one road directly connects the same pair of cities.
Output
On the first line, print the minimum total payment.
On the second line, print the city numbers visited by the chosen driving route, in order.
Inputs with no valid route are not given.