P5304 [GXOI/GZOI2019]旅行者

xht · 2019-04-17 20:32:14 · 题解

题目地址：P5304 [GXOI/GZOI2019]旅行者

这里是官方题解

一个图 n 点 m 条边，里面有 k 个特殊点，问这 k 个点之间两两最短路的最小值是多少？

n \leq 10^5, m \leq 5 * 10 ^5

假设我们把特殊点分成 A,B 两个集合，新建 s 连 A 集合的所有点，边权 0 ，新建 t 连接 B 集合里的所有点，边权 0 ，那么 s 到 t 的最短路就是 A,B 集合点之间的最短路的最小值。

那么对于 k 个特殊点，我们枚举二进制里的第 i 位，把二进制第 i 位是 0 的点放在 A ， 1 的点放在 B ，用以上方法跑一个最短路。

然后跑 log\ n 次最短路之后，所有最短路的最小值就是最终答案。

原理是，假设 k 个特殊点里最近的是 x 和 y ，那么 x 和 y 一定有一个二进制位不一样，那么他们肯定在那次分组的时候被放进了不同的集合，从而肯定被算进了最后的答案之中最短路。

#include <bits/stdc++.h>

const int MAXN = 100010, MAXM = 700010;

struct Edge {
    int y, z;
    Edge *next;
}*a[MAXN], POOL[MAXM], *ptr, *back[MAXN];

void AddEdge(int x, int y, int z) {
    Edge *tmp = ptr++;
    tmp->y = y;
    tmp->z = z;
    tmp->next = a[x];
    a[x] = tmp;
}

int n, nodes[MAXN], k, s, t;
long long dis[MAXN];

long long dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    std::priority_queue<std::pair<long long, int> > Q;
    Q.push(std::make_pair(0, s));
    for (int i = 1; i < n + 2; i++) {
        while (!Q.empty() && dis[Q.top().second] != -Q.top().first) Q.pop();
        if (Q.empty()) break;
        int now = Q.top().second;
        Q.pop();
        for (Edge *p = a[now]; p; p = p->next)
            if (dis[p->y] > dis[now] + p->z)
                Q.push(std::make_pair(-(dis[p->y] = dis[now] + p->z), p->y));
    }
    return dis[t];
}

int main(int argc, char* argv[]) {
    int T;
    scanf("%d", &T);
    while (T--) {
        ptr = POOL;
        memset(a, 0, sizeof a);
        int m;
        scanf("%d%d%d", &n, &m, &k);
        while (m--) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            AddEdge(x, y, z);
        }
        for (int i = 1; i <= k; i++) scanf("%d", nodes + i);

        long long Ans = ~0ull>>1;
        s = n + 1, t = n + 2;
        for (int i = 0; (1 << i) <= k; i++) {
            Edge *backup = ptr;
            memcpy(back, a, (sizeof a[0]) * (n + 3));
            for (int j = 1; j <= k; j++) if (j & (1 << i)) {
                    AddEdge(s, nodes[j], 0);
                } else {
                    AddEdge(nodes[j], t, 0);
                }
            Ans = std::min(Ans, dijkstra());
            ptr = backup;
            memcpy(a, back, (sizeof a[0]) * (n + 3));
            for (int j = 1; j <= k; j++) if (j & (1 << i)) {
                    AddEdge(nodes[j], t, 0);
                } else {
                    AddEdge(s, nodes[j], 0);
                }
            Ans = std::min(Ans, dijkstra());
            ptr = backup;
            memcpy(a, back, (sizeof a[0]) * (n + 3));
        }
        printf("%lld\n", Ans);
    }
    return 0;
}