4456 Nearest Maintenance Point
时间限制2 S
内存限制128 MB
通过率11.1%(1 / 9)
题目描述
A county consists of n cities (labeled 1, 2, …, n) connected by some bidirectional roads. Each road connects a pair of distinct cities. A robot company has built maintenance points in some cities. Now, they need your help to write a program to query the nearest maintenance point to a specific city.
输入格式
There will be at most 200 test cases. Each case begins with four integers n, m, s, q(2 ≤ n ≤ 104, 1 ≤ m ≤ 5 × 104, 1 ≤ s ≤ min {n, 1000}, 1 ≤ q ≤ min {n, 1000}), the number of cities, the number of roads, the number of cities which have maintenance points and the number of queries. Then m lines contain the descriptions of roads. Each of them contains three integers ui, vi, wi(1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 1000), denoting there is a road of length wi which connects city ui and vi. The next line contains s integers, denoting the cities which have maintenance points. Then q lines contain the descriptions of queries. Each of them contains one integer denoting a specific city. The size of the whole input file does not exceed 6MB.
输出格式
For each query, print the nearest city which has a maintenance point. If there are multiple such cities, print all of them in increasing order separated by a single space. It is guaranteed that there will be at least one such city.
输入输出样例
输入复制
4 4 2 3
1 2 1
2 3 2
2 4 1
4 3 2
1 3
3
2
4输出复制
3
1
1 3来源