| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 35 | 29 | 24 | 85.714% |
One magical night Patrik and Josip were talking about the number 42 and the meaning of life. They were interrupted by the famous lady voice in the tram: The next stop is Jordanovac. Patrik and Josip were distracted by this common sentence and started discussing:
Patrik: It is a very short ride between Joranovac and Maksimir, isn’t it?
Josip: It is, but the ride between Mašićeva and Kvatrić is way shorter.
Patrik: Really? I disagree.
Josip: I wonder, which is the shortest ride between all stations?
Paula, a big public traffic transport, was carefully listening to their conversation. The problem of finding the shortest ride interested her so much that she stayed in the tram longer than she intended just to listen to their conversation.
At each station (except for the first one, when they entered the tram) one of the following two things happened:
But before Paula could hear their conclusion about which ride was the shortest, they left the tram! Luckily, Paula remembers all their statements. Now she needs your help! Help her find the duration of the shortest ride and between which two stations the tram drove on that ride.
The first line contains the integer n (2 ≤ n ≤ 1 000), the number of tram stations.
The i-th of the following n − 1 lines contains the information about station i + 1 in one of the following formats:
Patrik ti – Duration of the ride between station 1 and station i + 1 is ti (1 ≤ ti ≤ 109)Josip yi ti – Duration of the ride between station y and station i + 1 is ti (yi < i + 1, 1 ≤ ti ≤ 109)Every station will be in a distinct position.
In one line output three numbers: t, x1, x2, the duration of the shortest ride and the indices of the starting and ending stations of that ride.
If multiple solutions exist, print the one with the smallest indices of the stations.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | ti ≤ 1 000 |
| 2 | 13 | Every sentence was said by Patrik. |
| 3 | 25 | No additional constraints. |
4 Patrik 3 Patrik 5 Josip 1 7
2 2 3
2 Josip 1 5
5 1 2
5 Patrik 4 Josip 2 4 Josip 2 6 Josip 4 2
2 3 4
Clarification of the first example: The tram drove for 3 minutes from the first to the second station, and 5 from the first to the third. We can conclude that from the second to the third station it took 2 minutes, which is the shortest ride.
Clarification of the third example: The ride between the fourth and fifth station is also 2 minutes but, because they have greater indices, only the 2 3 4 solution is accepted.