Castle Black Patrols
All submissions for this problem are available.
The survivors of the ranging beyond the Wall have decided to patrol castle Black every night. With death marching on the Wall as winter draws near each patrol group has agreed it will patrol particular passages of the castle. They will patrol all passages that will enable them to begin at a particular point of the castle and return to it after their patrol. Each patrol group will patrol each passage only once. The men of castle black will patrol all such possible patrol paths.
The castle can be thought to be of made junctions and passages. Junctions are places where 2 or more passages meet.
However there is one problem. The men want their patrol passages to be lit with weirwood - a very special kind of wood that keeps away the dead. The amount of weirwood required to light each passage depends on the passage. They have decided to light at least one passage of their patrol with weirwood, for the night is dark and full of terrors.
You are Samwell Tarly, a steward of the Night's Watch and since weirwood is a rare thing Maester Aemon has asked you to calculate the least amount of weirwood required per night given the Castle Black's description.
First line of the input contains T - the number of test cases. There is a blank line at the beginning of each test case.
First line of each test case consists of 2 numbers N M
N - number of junctions. Each junction for simplicity is given a number between 1 and N inclusive.
M - number of passages.
M lines follow each describing a passage. Each line consists of 3 numbers X Y Z
X and Y are the junctions the passage connects and Z is the number of logs of weirwood required to light the passage for one night.
The minimum logs of weirwood required per night to make sure the patrols feel safe.
Answer to each test case must be on a line of its own.
1 <= T <= 10
3 <= N <= 1000
3 <= M <= 400000
1 <= X, Y <= N
1 <= Z <= 10000
Large I/O. Use fast I/O routines.
Input: 1 6 7 1 2 8 2 4 5 4 6 7 6 5 2 5 3 3 3 4 1 1 3 4 Output: 3
Here there are 3 patrol paths:
(1-2, 2-4, 4-3, 3-1)
(3-4, 4-6, 6-5, 5-3)
(1-3, 3-5, 5-6, 6-4, 4-2, 2-1)
Passages (3 4) and (6 5) need to be light up so that the patrol units feel safe during their patrols of the castle.
|Time Limit:||0.2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions