CANDN - Charly And Nito

no tags 

Charly and Nito are friends and they like to be together at a nice bar in Palermo Hollywood.
About at 3 a.m. they start to feel sleepy and want to go home. They want to get home quickly
so each of them uses a path that minimizes the distance to his home. However, Charly and
Nito also like to walk together while they talk about the “good old times”, so they want to
walk together as much as possible.
Charly and Nito live in a city that can be modeled as a set of streets and junctions. Each
street connects a pair of distinct junctions and can be walked in both directions. No two streets
connect the same pair of junctions. Charly and Nito do not live together, and they do not live
at the bar. There is at least one path from the bar to Charly’s home; the same occurs with
Nito’s home.
Given information about the streets and junctions in the city, the locations of the bar, Charly’s
home and Nito’s home, you must tell Charly and Nito the maximum distance that they can
walk together without forcing them to walk more than the minimum distance from the bar to
their respective homes. Charly and Nito also want to know how much each of them will walk


The input contains several test cases, each one described in several lines. The first line of
each test case contains five integers J, B, C, N and S separated by single spaces. The value
J is the number of junctions in the city (3 ≤ J ≤ 5000); each junction is identified by an
integer number between 1 and J. The values B, C and N are the identifiers of the junctions
where the bar, Charly’s home and Nito’s home are located, respectively (1 ≤ B, C, N ≤ J);
these three junction identifiers are different. The value S is the number of streets in the city
(2 ≤ S ≤ 150000). Each of the next S lines contains the description of a street. Each street
is described using three integers E1 , E2 and L separated by single spaces, where E1 and E2
identify two distinct junctions that are endpoints of the street (1 ≤ E1 , E2 ≤ J), and L is the
length of the street (1 ≤ L ≤ 104 ). You may assume that each street has a different pair of
endpoints, and that there exist paths from junction B to junctions C and N . The last line
of the input contains the number −1 five times separated by single spaces and should not be
processed as a test case.


For each test case output a single line with three integers T , C and N separated by single
spaces, where T is the maximum distance that Charly and Nito can walk together, C is the
distance that Charly walks alone, and N is the distance that Nito walks alone.


5 3 2 1 6
3 4 10
4 5 10
5 1 3
5 2 4
1 3 23
2 3 24
8 1 7 8 8
1 2 1
2 4 1
2 3 1
4 5 1
3 5 1
5 6 1
6 8 1
6 7 1
-1 -1 -1 -1 -1


20 4 3
4 1 1

hide comments
nadstratosfer: 2019-12-03 09:22:37

Great problem. Plenty of headache with pen and paper to get the right solution, then some more trying to understand a weird bug that I finally had to circumvent without learning why it happens. Not much score for the work it cost me, but feels good to get past it.

Added by:Pablo Ariel Heiber
Time limit:3.146s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2007