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次查询，问距离某个点最近的特殊点的编号，如果有多个，升序输出。

题解

注意题目的数据范围，虽然点数和边数都达到了$10^4$，但是最多只有1000个特殊点和1000次查询，显然我们不能跑1000次dijkstra，但是我们可以转化一下。

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

每次查询都跑一次最短路的代价有点高，要么就考虑优化每次做最短路的代价（确实有比较好想到的优化的余地，但也有可能不难想到针对的措施，或者真的优化的非常好也是可以的），要么就另辟蹊径。

发现可以直接从维修点一起开始跑最短路，这样一次跑完就能知道每个点距离维修点的最短距离了。对于输出结果的话，比较好写的是在Dijkstra状态转移的过程中直接用c++的bitset记录，或者跑完之后，每次查询dfs一下。

——官方题解

代码

#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);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        int st = 0;
        for (int i = 0; i < s; ++i)
        {
            scanf("%d", &spe[i]);
            flag[spe[i]] = true;
            ans[spe[i]].set(i); // 本身就是特殊点
            addedge(st, spe[i], 0); // 建立超级源
        }
        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对象的方法

bitset操作

The end.
2018-08-08 星期三