P5304:「GXOI/GZOI2019」旅行者 – 题解

主要思路

这个题还蛮神仙的，我很喜欢。

如果是做暴力的话，那么这个思路是很有限的。我们考虑换一种思路。既然最后的答案是要求 \(\Theta(k^2)\) 级别对的最短路，我们尝试把这个规模进行缩小，然后只求小规模的全局解（并不是求出所有最短路），然后多次求解之后可以得到全规模的全局解。

这里有一个解决小规模问题的思路：如果我们把点分成集合 \(A, B\)，然后源点 \(S\) 与集合 \(A\) 连零边、集合 \(B\) 向汇点 \(T\) 连零边。这样跑一边最短路可以解出所有 \((x, y), x \in A, y \in B\) 这样的最小解，那么规模就是 \(|A| \times |B|\)。

我们尝试让每次解决小规模问题时，独特的 \((x, y), x \in A, y \in B\) 的个数尽量多，这样就可以用尽可能少的次数去解决全局规模。这里用到的方法是做 \(\log_2 n\) 次，然后每次划分出 \(A, B\) 点集的依据为编号第 \(i\) 位是否为 \(01\)。

这样可以保证任意两个点至少会在一次划分中不在一个点集内，因为不存在两个编号相同的点。

// P5304.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, MAX_E = 7e5 + 200;

typedef long long ll;
typedef pair<ll, int> pli;

int T, n, m, kind, head[MAX_N], current, ui[MAX_E], vi[MAX_E], wi[MAX_E], start_pos, end_pos, pts[MAX_N];
bool vis[MAX_N];
ll dist[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_E];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}

void shortest_path()
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    priority_queue<pli> pq;
    pq.push(make_pair(0, start_pos)), dist[start_pos] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].weight)
                dist[edges[i].to] = dist[u] + edges[i].weight, pq.push(make_pair(-dist[edges[i].to], edges[i].to));
    }
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &m, &kind);
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &ui[i], &vi[i], &wi[i]);
        for (int i = 1; i <= kind; i++)
            scanf("%d", &pts[i]);
        ll ans = 2e18;
        for (int i = 0; (1 << i) <= kind; i++)
        {
            memset(head, -1, sizeof(head)), current = 0;
            for (int j = 1; j <= m; j++)
                addpath(ui[j], vi[j], wi[j]);
            start_pos = n + 1, end_pos = n + 2;
            for (int j = 1; j <= kind; j++)
                if (j & (1 << i))
                    addpath(start_pos, pts[j], 0);
                else
                    addpath(pts[j], end_pos, 0);
            shortest_path(), ans = min(ans, dist[end_pos]);
        }
        for (int i = 0; (1 << i) <= kind; i++)
        {
            memset(head, -1, sizeof(head)), current = 0;
            for (int j = 1; j <= m; j++)
                addpath(ui[j], vi[j], wi[j]);
            start_pos = n + 1, end_pos = n + 2;
            for (int j = 1; j <= kind; j++)
                if (!(j & (1 << i)))
                    addpath(start_pos, pts[j], 0);
                else
                    addpath(pts[j], end_pos, 0);
            shortest_path(), ans = min(ans, dist[end_pos]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}