I |
Innovative Procession Management |
It’s
FIFA World Cup 2010. The whole world is waiting for the greatest event on the
planet. Since huge number of people will come to South Africa for the world
cup; it’s quite tough for them to maintain the flow of the people as well as
the traffic. That’s why they are planning to forbid vehicles to use some roads.
But if all the roads are forbidden then people would be in trouble.
The
World Cup authority has divided South Africa into n junctions and m one
way roads. Before each match, the authority will consider some junctions as
interesting junctions, where people will get together and set out for the
stadium in processions. Now each procession will try to use the shortest path
towards the stadium. That’s why the World Cup authority wants to forbid
vehicles in the roads which may be used by the processions.
The
idea is as follows. They will first find the shortest path amongst the paths
from the interesting junctions to the stadium. They will block all the roads in
the path. If there are multiple shortest paths from one or multiple interesting
junctions to the stadium, they will block all of them. They will send some
vehicles along the paths which will put notice boards to the roads such that no
vehicles can go through. After that they will search for more shortest-paths
considering the blocked roads and send vehicles for the paths (if any). They
will continue blocking the roads until no path is found.
Now
your task is to solve the problem for them.
Input starts with an integer T (<= 100), denoting the number of test cases.
Each
case starts with a blank line. The next line contains three integers n (2 <= n <= 100), m (0 <= m <=
10000), and S (1 <= S < n).
S is the total number of interesting
junctions.
The
next line will contain S + 1
different integer (each of them lies between 1 and n) separated by
spaces, where the first S integers
denote the interesting junctions, and the last one denotes the stadium.
Each
of the next m lines will contain 3
integers u v w (1 <= u, v <= n, u
!= v, 1<=w<=10000) meaning that there is a road from u to v, and the length is w.
If multiple roads are listed for same junctions in either direction, you can
assume that the roads are different.
For
each case print the case number in a single line. If no path is found then
print “No road to block”. If a
shortest path is found then print the path cost c as “The path cost is c”.
After that report the roads that are blocked in u v w form (as in input). They should be listed in ascending order
based on u; for same u, based on v. Report all the shortest path costs and the roads in similar
format. Check the samples for more details.
Sample Input |
Sample Output |
3 2 1 1 1 2 2 1 10 3 5 2 1 3 2 2 1 10 1 2 20 1 2 20 1 2 30 3 2 30 4 4 2 1 2 4 1 4 10 2 4 10 1 3 20 3 4 10 |
Case 1: No road to block Case 2: The path cost is 20 1 2 20 1 2 20 The path cost is 30 1 2 30 3 2 30 Case 3: The path cost is 10 1 4 10 2 4 10 The path cost is 30 1 3 20 3
4 10 |
Problemsetter: jane Alam Jan, Special Thanks: Manzurur
Rahman Khan