# CSU2005 Nearest Maintenance Point（最短路+bitset）

## Nearest Maintenance Point

• Time Limit: 2 Sec
• Memory Limit: 128 Mb
• Submitted: 126
• Solved: 8

### 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 ≤ 10^4, 1 ≤ m ≤ 5 × 10^4$, 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.

### 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

### 链接

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2005

### 题意

n个点m条边的无向带权图，其中有s个特殊点，现有q次查询，问距离某个点最近的特殊点的编号，如果有多个，升序输出。

### 题解

• 建立一个超级源(0)，和每个特殊点连边，边权为0，源点到每个点的最短距离$\rightarrow$特殊点到每个点的最短距离$\rightarrow$每个点距离特殊点的最短距离
• 在dijkstra的状态转移中，使用bitset记录距离每个点最近的特殊点编号

——官方题解

### 代码

StatusAccepted
Time932ms
Memory6112kB
Length3046
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <bitset>
#include <vector>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 10010;
const int maxm = 50010;
int n, m, s, q;
bool vis[maxn], flag[maxn]; // flag 标记特殊点
int dist[maxn], spe[1010], ANS[maxn]; // 最短距离、特殊点编号、答案
bitset <1010> ans[maxn]; // 记录每个点距离最近的特殊点
struct qnode
{
int v, c;
qnode (int _v = 0, int _c = 0):v(_v), c(_c){}
bool operator < (const qnode & r) const
{
return c > r.c;
}
};
struct Edge
{
int v, cost;
Edge(int _v = 0, int _cost = 0):v(_v), cost(_cost){}
};
vector <Edge> E[maxn];

void addedge(int u, int v, int w)
{
E[u].push_back(Edge(v, w));
}

void init()
{
memset(flag, 0, sizeof(flag));
for (int i = 0; i <= n; ++i)
{
E[i].clear();
ans[i].reset();
}
}

void dijkstra(int start)
{
memset(vis, 0, sizeof(vis));
for (int i = 0; i <= n; ++i)
dist[i] = inf;
priority_queue <qnode> que;
while (!que.empty())
que.pop();
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty())
{
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u])
continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); ++i)
{
int v = E[u][i].v;
int cost = E[u][i].cost;
if (vis[v])
continue;
if (dist[v] > dist[u] + cost) // 状态转移
{
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
if (flag[v]) // v本身就是特殊点
continue;
ans[v].reset(); // 重置
for (int j = 0; j < s; ++j) // 更新答案
{
if (ans[u].test(j)) // 得到距离上一个节点u最近的特殊点
ans[v].set(j);
}
}
else if (dist[v] == dist[u] + cost) // 有多个特殊点距离v最近
{
for (int j = 0; j < s; ++j)
{
if (ans[u].test(j))// 得到距离上一个节点u最近的特殊点
ans[v].set(j);
}
}
}
}
}

int main()
{
int u, v, w;
while (scanf("%d%d%d%d", &n, &m, &s, &q) != EOF)
{
init();
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
}
int st = 0;
for (int i = 0; i < s; ++i)
{
scanf("%d", &spe[i]);
flag[spe[i]] = true;
ans[spe[i]].set(i); // 本身就是特殊点
}
dijkstra(st);
while (q--)
{
scanf("%d", &u);
int k = 0;
for (int i = 0; i < s; ++i)
{
if (ans[u].test(i)) // 最后结果
ANS[k++] = spe[i];
}
sort(ANS, ANS + k);
for (int i = 0; i < k; ++i)
printf("%d%c", ANS[i], i == k - 1 ? '\n' : ' ');
}
}
return 0;
}

### 初始化bitset对象的方法

bitset b;b有n位，每位都为0
bitset b(u);b是unsigned long型u的一个副本
bitset b(s);b是string对象s中含有的位串的副本
bitset b(s, pos, n);b是s中从位置pos开始的n个位的副本

### bitset操作

b.any()b中是否存在置为1的二进制位？
b.none()b中不存在置为1的二进制位吗？
b.count()b中置为1的二进制位的个数
b.size()b中二进制位的个数
b[pos]访问b中在pos处的二进制位
b.test(pos)b中在pos处的二进制位是否为1？
b.set()把b中所有二进制位都置为1
b.set(pos)把b中在pos处的二进制位置为1
b.reset()把b中所有二进制位都置为0
b.reset(pos)把b中在pos处的二进制位置为0
b.flip()把b中所有二进制位逐位取反
b.flip(pos)把b中在pos处的二进制位取反
b.to_ulong()用b中同样的二进制位返回一个unsigned long值
os << b把b中的位集输出到os流

The end.
2018-08-08 星期三