Subway upgrade
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 69 Accepted Submission(s): 15
Problem Description
As we all know, one of the most important inventions for modern-day public transportation is the subway, which brings much convenience to our daily-life and saves us from the congested traffic.
However, to hold the next ACM regional contest, you, as the mayor of city X, decided to upgrade the subway system of that city. There are some stations and roads in the city now, any road has a cost. To save money, you decided not to construct every road, but to make sure that there exist a path between every two stations.
Sorry, the mission isn't completed. You know, there are n stations in the city,some contestants visit other stations regularly to admire some so-called big cows. Being naturally averse to spending hours each day on commuting, you should help them to find a place to live for which the total travel time is minimal.
Every road has an ID, from 1 to m. If there are multiple approaches leading to the same minimal cost, the mayor prefers the one of which road IDs selected holds the smallest lexicographic order. For instance, rebuilding ID ( 1 3 5) and ID (2 4 5) will both ensure the minimum cost,the mayor will choose the former one.
However, to hold the next ACM regional contest, you, as the mayor of city X, decided to upgrade the subway system of that city. There are some stations and roads in the city now, any road has a cost. To save money, you decided not to construct every road, but to make sure that there exist a path between every two stations.
Sorry, the mission isn't completed. You know, there are n stations in the city,some contestants visit other stations regularly to admire some so-called big cows. Being naturally averse to spending hours each day on commuting, you should help them to find a place to live for which the total travel time is minimal.
Every road has an ID, from 1 to m. If there are multiple approaches leading to the same minimal cost, the mayor prefers the one of which road IDs selected holds the smallest lexicographic order. For instance, rebuilding ID ( 1 3 5) and ID (2 4 5) will both ensure the minimum cost,the mayor will choose the former one.
Input
First,a number t,indicating the number of the testcases.
For every testcase, there is a number n and m,n(1<=n<=50000) indicating the number of cities,whereas m (0<=m<=500000) indicating the number of roads.
then m lines follow each lines contains three integers a,b,c.(1<=a,b<=n&&a!=b,1<=c<=10000)which means there is a road from a to b whose cost is c.
For every testcase, there is a number n and m,n(1<=n<=50000) indicating the number of cities,whereas m (0<=m<=500000) indicating the number of roads.
then m lines follow each lines contains three integers a,b,c.(1<=a,b<=n&&a!=b,1<=c<=10000)which means there is a road from a to b whose cost is c.
Output
First the minimum cost.If doesn't exist,only output "Poor mayor."(without quotes)
Then output the answer and all the candidate stations.
Then output the answer and all the candidate stations.
Sample Input
3 3 3 1 2 10 2 3 20 3 1 15 3 1 1 2 15 2 1 1 2 15
Sample Output
25 1 50 Poor mayor. 15 1 2 30 Hint: In the first sample we use road 1 and 3 ,the minimus cost is 10+15=25 and we get a new graph 3-1-2,city 1 is the best answer ,2*10+2*15=50 Whereas the third, we can't get city 1,2,3 connected. In the last, we choose the road 1,the minimus cost is 15 and we get a new graph 1-2,both city 1 and city 2 are the best answer ,2*15=30
Author
daizhenyang@BUPT