题解：P11564 【MX-X7-T5】[LSOT-3] 你的列车是生存战略

__camelia · 2026-10-20 11:11:42 · 题解

P11564 你的列车是生存战略 题解

题意

有 n 个车站，第 i 个车站有两个标号 c_i,d_i。

任意两个车站 i,j 之间都有一条普通列车双向线路，耗时

另外有 m 条单向特快线路 u\to v，耗时 w。

求从车站 1 到每个车站的最短路。

核心思路

注意到特快列车可以通过直接加入单向边来处理，

瓶颈在于普通列车，点数达到了 10^6 级别，直接连边建完全图会连出 \frac {n \times (n - 1)} 2 约 10 ^ {12} 条边，直接爆炸。

由于 k \le 14，即 2 ^ k \le 16384 较小，考虑从二进制掩码入手。

普通列车的代价只和两个掩码有关：

分别建立一条“或运算通道”和一条“与运算通道”，把一次普通列车拆成：

1. 从起点车站进入虚拟图；
2. 在虚拟图中移动到对应的掩码；
3. 从虚拟图离开到终点车站。

两条通道分别计算 a_{c_i\mid c_j} 和 b_{d_i\&d_j}。由于两条通道都可以从 i 到 j，Dijkstra 会自然选择较小的一条，从而等价于取 \min。

虚拟图

令 S=2^k，建立四层掩码节点：

节点编号可以这样分配：

int s = 1 << k;
int orup = n + 1; // or_up
int ordn = orup + s;// or_down
int andd = ordn + s;// and_down
int andu = andd + S;// and_up
int v = andu + S - 1;// 总点数

或运算

目标是计算：

建立以下有向边：

1. 车站 i 进入 orup_{c_i}，边权为 a_{c_i}。
2. 如果 x 的第 b 位为 0，则

边权为

因为 a 单调不降，所以边权非负。

2. 如果 x 的第 b 位为 1，则

边权为 0。

从 i 到 j 时，令

沿 orup 从 c_i 一位一位加到 u，总代价为

然后切换到 ordn，免费向下走到 c_j。因此这条路径的代价正好是

与运算

目标是计算：

建立以下有向边：

1. 车站 i 进入 andd_{d_i}，边权为 b_{d_i}。
2. 如果 x 的第 b 位为 1，则

边权为

因为 b 单调不升，所以边权非负。

2. 如果 x 的第 b 位为 0，则

边权为 0。

从 i 到 j 时，令

沿 andd 从 d_i 删位到 v，总代价为

然后切换到 andu，免费向上走到 d_j。因此这条路径的代价正好是

不能把所有掩码边建成无向边。

以或运算为例，如果同一个掩码图既允许付费向上，又允许免费向下，那么可以：

1. 先免费向下；
2. 再付费向上；

最后到达一个原本不应该达到的掩码。

这会得到小于真实 a_{c_i\mid c_j} 的错误路径。

因此必须强制：

• 或运算：先付费向上，再免费向下；
• 与运算：先付费向下，再免费向上。

两层虚拟点就是为了固定这个顺序。

复杂度

虚拟点数为

边数为

在虚拟图上跑 Dijkstra：

所有边权非负，因此 Dijkstra 正确。

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 6e6 + 5;
const int mod = 998244353;

int n,m,k;
int tot,head[N];
struct edge {
    int v,w,nxt;
} e[N];
void add_edge(int u,int v,int w){
    e[++tot].v = v;
    e[tot].w = w;
    e[tot].nxt = head[u];
    head[u] = tot;
}

int v;
const int inf = 4e18;

void dijkstra(){
    vector<int> dis(n + v + 1,inf);
    dis[1] = 0;
    bitset<2000006> vis;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push({0,1});
    while(!q.empty()){
        auto [ds,u] = q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = e[i].nxt){
            int v = e[i].v,w = e[i].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                q.push({dis[v],v});
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout << dis[i] << ' ';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    int s = (1 << k);
    vector<int> c(n + 1,0),d(n + 1,0),a(16400,0),b(16400,0);
    for(int i = 1; i <= n; i++){
        cin >> c[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> d[i];
    }
    for(int i = 0; i < s; i++){
        cin >> a[i];
    }
    for(int i = 0; i < s; i++){
        cin >> b[i];
    }
    for(int i = 1; i <= m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        add_edge(u,v,w);
    }
    int orup = n + 1;
    int ordn = orup + s;
    int andd = ordn + s;
    int andu = andd + s;
    v = andu + s - 1;
    for(int i = 1; i <= n; i++){
        add_edge(i,orup + c[i],a[c[i]]);
        add_edge(ordn + c[i],i,0);
        add_edge(i,andd + d[i],b[d[i]]);
        add_edge(andu + d[i],i,0);
    }
    for(int i = 0; i < s; i++){
        for(int bit = 0; bit < k; bit++){
            if(!(i >> bit & 1)){
                int j = i | (1 << bit);
                add_edge(orup + i,orup + j,a[j] - a[i]);
                add_edge(andu + i,andu + j,0);
            }
            else{
                int j = i ^ (1 << bit);
                add_edge(ordn + i,ordn + j,0);
                add_edge(andd + i,andd + j,b[j] - b[i]);
            }

        }
        add_edge(orup + i,ordn + i,0);
        add_edge(andd + i,andu + i,0);
    }

    dijkstra();

    return 0;
}

声明：

本文章使用了 deepseek 进行润色，但代码与大部分文字为人类提供，保证人类贡献大于 AI。