MENU

CSU2005 Nearest Maintenance Point(最短路+bitset)

2018 年 08 月 08 日 • 阅读: 1122 • 图论阅读设置

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一下。

——官方题解

代码

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);
            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 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 星期三
最后编辑于: 2018 年 08 月 19 日