问题描述 :
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
