시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 26 | 10 | 9 | 75.000% |
When driving a hire car in the UK in winter, it has sometimes struck me that the navigation system’s option of avoiding major roads is almost the opposite of what I want. Major roads tend to be less hazardous, being more likely to be cleared of snow in cold winters and less likely to be flooded in warm winters.
I need to get to Hazel’s house for afternoon tea. Given my emphasis on safety, each road will have a hazard rating and a length. I want a route that minimises the maximum hazard rating encountered on the route. Out of all the routes that minimise the maximum hazard rating encountered, I want one that minimises the total length of the route. Each road is two-way. There is at least one route from my house to Hazel’s house. What is an optimal route to get from my house to Hazel’s house?
The first line contains 4 integers N (2 ≤ N ≤ 200 000), which is the number of locations, M (1 ≤ M ≤ 200 000), which is the number of roads, S (1 ≤ S ≤ N), which is the location of my house, and E (1 ≤ E ≤ N), which is the location of Hazel’s house (and is not equal to S).
The next M lines describe the roads. Each of these lines contains 4 integers A (1 ≤ A ≤ N), which is one endpoint of the road, B (1 ≤ B ≤ N, A 6= B), which is the other endpoint of the road, H (1 ≤ H ≤ 108), which is the hazard rating of the road, and L (1 ≤ L ≤ 108), which is the length of the road.
Display the maximum hazard rating of an optimal route and its total length.
4 5 1 4 1 2 1 5 2 4 2 10 1 3 2 5 3 4 2 5 1 4 5 4
2 10
3 3 1 3 1 2 5 1 2 3 5 1 1 3 1 4
1 4
2 2 1 2 1 2 3 4 2 1 2 6
2 6