2014
03-06

# Effective Government Spokesman

Nowaday, supermarket makes our life more convenient. We can buy a lot of things in supermarket.
Now in a city, the government has built two supermarkets. And the citizens want to know whether the sum of distance between their house and the supermarket is the smallest. Let’s describe the problem more precisely. We define L1 is the distance from this house to supermarket A, L2 is the distance from this house to supermarket B, and D = L1 + L2. If there is no other house which has smaller D than this house, then this house is on the shortest road between supermarket A and supermarket B. Now the government needs your help to answer the citizen’s question: Whether their house is built on the shortest path between supermarket A and supermarket B.

The first line of input is a single integer T, indicating the number of test cases. Following that are exactly t cases. In each case, the first line contains two integers: N, the number of houses, and M, the number of roads. Then M lines will follow, each of which contains three integers A B C, indicating there is a road between place A and B, whose length is C. Please note that all roads are undirected. The last line contains two integers A, B (A != B) separated by a space, indicating the location of the two supermarket. The next line contains an integer Q, the number of questions that citizens had asked. Then Q lines follow, each line contain a integer p, indicate the number of the house. There is only one road between any pair of places. There must exists a path between two places.

1<= T <= 50;
5 <= N <= 100;
N � 1 <= M <= (N * (N – 1)) / 2;
1<= A, B, Q, Q<= N;
1 <= C < 1000;

The first line of input is a single integer T, indicating the number of test cases. Following that are exactly t cases. In each case, the first line contains two integers: N, the number of houses, and M, the number of roads. Then M lines will follow, each of which contains three integers A B C, indicating there is a road between place A and B, whose length is C. Please note that all roads are undirected. The last line contains two integers A, B (A != B) separated by a space, indicating the location of the two supermarket. The next line contains an integer Q, the number of questions that citizens had asked. Then Q lines follow, each line contain a integer p, indicate the number of the house. There is only one road between any pair of places. There must exists a path between two places.

1<= T <= 50;
5 <= N <= 100;
N � 1 <= M <= (N * (N – 1)) / 2;
1<= A, B, Q, Q<= N;
1 <= C < 1000;

2
5 5
1 2 1
2 3 1
3 5 1
1 4 1
4 5 2
1 5
5
1
2
3
4
5

5 5
1 2 1
2 3 1
3 5 1
1 4 1
4 5 3
1 5
5
1
2
3
4
5

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮