CSU 2005: Nearest Maintenance Point（Dijkstra + bitset）

Description

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.

Input

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 u i , v i , w i (1 ≤ u i , v i ≤ n , u i ≠ v i , 1 ≤ w i ≤ 1000), denoting there is a road of length w i which connects city u i and v i . 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.

Output

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.

Sample Input

4 4 2 3

1 2 1

2 3 2

2 4 1

4 3 2

1 3

3

2

4

Sample Output

3

1

1 3

题目大意:有n个城市，m条边将一些城市连接起来，现在有s个城市维护点，q次查询，现在对于每一次查询的城市，输出离他最近的城市维护点，如果有多个则按递增顺序打印。
思路: 把s个城市维护点当起点搜一下最短路，其中用bitset来维护其他城市距离维护点最近的那个起点，对于城市x来说，若有多个起点城市到它的最短距离是相等的就用或运算将之存在bitset，否则直接将最短的那一个维护点赋值给x
　　代码上也做了一些注释（如果对于bitset不是很熟悉的可以向大家推荐一篇感觉还不错的博客。http://www.cppblog.com/ylfeng/archive/2010/03/26/110592.html）

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<bitset>

 #include<vector>

 #include<queue>

 using namespace std;

 const int INF =  << ;

 const int maxn = ;

 struct node {

     int to, cost;

     node() {}

     node(int a, int b) :to(a), cost(b) {}

     bool operator<(const node&a)const {

         return cost > a.cost;

     }

 };

 vector<node>e[maxn];

 bitset<>bt[maxn];

 int n, m, s, q;

 int dis[maxn], cha[maxn], vis[maxn];

 void Dijkstra()

 {

     priority_queue<node>Q;

     for (int i = ; i <= n; i++) {

         dis[i] = INF; bt[i].reset();//初始化距离和清空bitset表

         vis[i] = ;

     }

     for (int i = ; i <= s; i++) {

         dis[cha[i]] = ;

         Q.push(node(cha[i], dis[cha[i]]));

         bt[cha[i]][i] = ;//bt[i][j] = 1 代表第i个城市最近的城市维护点是第j个

     }

     while (!Q.empty()) {

         node t = Q.top(); Q.pop();

         if (vis[t.to])continue;

         vis[t.to] = ;//对于每一个点我们只需要以他为起点遍历一次就ok，避免大量的重复计算

         for (int i = ; i < e[t.to].size(); i++) {

             int tmp = e[t.to][i].to;

             int ct = e[t.to][i].cost;

             if (dis[tmp] > dis[t.to] + ct) {

                 dis[tmp] = dis[t.to] + ct;

                 Q.push(node(tmp, dis[tmp]));

                 bt[tmp] = bt[t.to];//如果有比当前更近的城市维护点则将更近的维护点赋值给现在的点

             }

             else if (dis[tmp] == (dis[t.to] + ct))

                 bt[tmp] |= bt[t.to];//如果有多个城市维护点的距离相同就取或赋值

         }

     }

 }

 int main()

 {

     while (scanf("%d%d%d%d", &n, &m, &s, &q) != EOF) {

         for (int i = ; i <= n; i++)e[i].clear();

         for (int a, b, c, i = ; i < m; i++) {

             scanf("%d%d%d", &a, &b, &c);

             e[a].push_back(node(b, c));

             e[b].push_back(node(a, c));

         }

         for (int i = ; i <= s; i++)scanf("%d", &cha[i]);

         sort(cha + , cha + s + );//因为题目要我们如果有多个点满足要求，则递增输出，所以我们可以事先排个序

         Dijkstra();

         int x;

         while (q--) {

             int a[], cnt = ;

             scanf("%d", &x);

             for (int i = ; i <= s; i++)

                 if (bt[x][i])//对于s个城市维护点来说，若bt[x][i]==1则代表第i个城市到x的距离是最近的

                     a[++cnt] = cha[i];

             for (int i = ; i < cnt; i++)

                 printf("%d ", a[i]);//最后按格式输出即可

             printf("%d\n", a[cnt]);

         }

     }

     return ;

 }