洛谷P3451 [POI2007]ATR-Tourist Attractions 题解

题目链接：P3451 [POI2007]ATR-Tourist Attractions

题意：

给出一张有 \(n\) 个点 \(m\) 条边的无向图，每条边有边权。

你需要找一条从 \(1\) 到 \(n\) 的最短路径，并且这条路径在满足给出的 \(g\) 个限制的情况下可以在所有编号从 \(2\) 到 \(k+1\) 的点上经过。

每个限制条件形如 \(r_i, s_i\)，表示经过 \(s_i\) 之前必须曾经过 \(r_i\) 。

输入格式：

第一行三个整数 \(n,m,k\)。

之后 \(m\) 行，每行三个整数 \(p_i, q_i, l_i\)，表示在 \(p_i\) 和 \(q_i\) 之间有一条权为 \(l_i\) 的边。

之后一行一个整数 \(g\)。

之后 \(g\) 行，每行两个整数 \(r_i, s_i\)，表示一个限制条件。

输出格式：

输出一行一个整数，表示最短路径的长度。

数据范围：

\(2\le n\le2\times10^4,~1\le m\le2\times10^5,~0\le k\le\min(20, n-2),~1\le p_i<q_i\le n\)

\(1\le l_i\le 10^3,~2\le r_i, s_i\le k+1, r_i\not=s_i\) ，数据保证不存在重边且一定有解。

注意到除了这几个必须经过的点和 \(1,n\) 以外，其他的点其实没有意义

因为我们在这几个点之间走来走去的时候，一定是走的最短路，所以我们先处理出这 \(k\) 个点的最短路。

考虑状压dp。这里需要特判一下 \(k=0\) 的情况，这个就是一个最短路的事。

设 \(f_{S,i}\) 表示停留在这 \(k + 1\) 个点的 \(i\) 上，已经过 \(2\) 到 \(k+1\) 的点的状态为 \(S\) 时的最小花费，则 \[ f_{j, S \cup\{j\}} \downarrow f_{i, S}+\operatorname{dist}(i, j) \] 其中 \(j\) 是符合条件的点。最后的答案即为 \(f_{i, U}+\operatorname{dist}(i, n)\) ，其中 \(U\) 为全集。

然后你会发现这题只有 64MiB 的空间，直接dp肯定要爆空间。那么怎么优化空间呢？

容易发现，状态 \(T\) 得到 \(S\) 的贡献，当且仅当 \(|S| \le |T| \le |S| + 1\) 。

因此我们可以把这些状态按他们的基数排序，并利用滚动数组的思想优化空间，具体见代码

时间复杂度 \(\mathcal{O}(km\log n + k^22^k)\)

空间复杂度 \(\mathcal{O}\left(2k\cdot\binom{k}{k/2} + 2^k\right)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f
#define popc(x) __builtin_popcount(x)
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e4 + 15))
#define M ((int)(4e5 + 15))
#define K 22
#define K2 ((int)((1 << 20) + 15))
#define L ((int)(2e5))

vector<int> vec[K];
int V,E,n,pos=1,head[N],p[K],dis[K][N],f[2][L][K],id[K2];
struct Edge { int u,v,w,next; } e[M];
void addEdge(int u,int v,int w) { e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
namespace cxy
{
    struct node { int u,dis; }; int C[21][21];
    bool operator<(node a, node b) { return a.dis > b.dis; }
    priority_queue<node> q;
    void Dijkstra(int st)
    {
        int *d = dis[st]; q.push({st,0}); d[st] = 0;
        for(int u,t; !q.empty(); )
        {
            u = q.top().u; t = q.top().dis; q.pop();
            if(t != d[u]) continue;
            for(int i = head[u]; i; i = e[i].next)
                if(d[e[i].v] > d[u] + e[i].w)
                {
                    d[e[i].v] = d[u] + e[i].w;
                    q.push({e[i].v, d[e[i].v]});
                }
        }
    }
    void init_vec()
    {
        for(int i = 0; i <= n; i++) C[i][0] = 1;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> V >> E >> n;
    for(int i = 1, u,v,w; i <= E; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 1; i <= n + 1; i++) cxy::Dijkstra(i);
    int m; cin >> m;
    for(int u,v; m--; ) { 
        cin >> u >> v; p[v] |= 1 << (u - 2);
    }
    int mx = (1 << n) - 1; cxy::init_vec();
    for(int i = 0; i <= n; i++) vec[i].reserve(cxy::C[n][i] + 5);
    for(int j = 0, c; j <= mx; j++) {
        c = popc(j); id[j] = vec[c].size(); vec[c].emplace_back(j);
    }
    memset(f[0], 0x3f, sizeof(f[0])); f[0][id[0]][1] = 0;
    for(int cnt = 1; cnt <= n; cnt++)
    {
        int now = cnt & 1, pre = now ^ 1;
        for(int i = 0; i < vec[cnt].size(); i++)
            for(int j = 1; j <= n + 1; j++) f[now][i][j] = INF;
        for(int j : vec[cnt - 1])
            for(int i = 1; i <= n + 1; i++) if(f[pre][id[j]][i] < INF) 
                for(int k = 2; k <= n + 1; k++) if(((~j) & p[k]) == 0)
                {
                    if((j | (1 << (k - 2))) == j) {
                        down(f[pre][id[j]][k], f[pre][id[j]][i] + dis[i][k]);
                    }else {
                        down(f[now][id[j | (1 << (k - 2))]][k], f[pre][id[j]][i] + dis[i][k]);
                    }
                }
    }
    int res = INF;
    for(int i = 1; i <= n + 1; i++)
        down(res, f[n & 1][id[mx]][i] + dis[i][V]);
    cout << res << '\n';
    return 0;
}