Railway Construction

1580E3400· legendary gm2.5s512 MB⌨ stdin/stdout

#brute force #constructive algorithms #data structures #graphs #shortest paths

Examples

Sample 1of 3

Input

Output

3
9

Sample 2of 3

Input

8 11 0
14 4 16 15 1 3 1 14
4 2 1
1 2 3
7 5 4
2 3 1
8 6 2
8 5 5
5 4 5
7 6 7
3 5 5
1 6 6
8 1 4

Output

Sample 3of 3

Input

10 16 8
29 1 75 73 51 69 24 17 1 97
1 2 18
2 3 254
2 4 546
2 5 789
5 6 998
6 7 233
7 8 433
1 9 248
5 10 488
2 6 1787
10 8 1176
3 8 2199
4 8 1907
2 10 1277
4 10 731
9 10 1047
1 11
1 9
8 8
1 3
2 19
9 5
9 4
7 6

Output

1580E.cpp

loading editor…

Ln 11·137 BGNU C++20 (64)

loading graph engine…