文化之旅

GitHub跳转原题关系图返回列表

把「已学文化集合」压进状态：状态 (国家, mask) 上跑 Dijkstra，并用忽略文化的地理最短距离做 A* 启发、两条必要条件预检快速判 -1。

OJ: roj

题目 ID: 3597

难度:提高

标签:搜索最短路状压dijkstrapython

创建: 2026-10-02 09:55

更新: 2026-10-10 11:30

前置题目
luogu P4779【模板】单源最短路径（标准版）B 直接复用 A 教的堆优化 Dijkstra 作核心引擎，只把状态从单点扩成 (国家, 已学文化集合)，额外叠加状压建模与 A* 剪枝。roj 1382最短路(Spfa)B 的核心引擎复用了 A 教的堆优化 Dijkstra 与「首次弹出即定型、命中终点提前返回」这一步：A 用来定型单个点，B 把它搬到 (国家,已学文化集合) 状态图上，首次弹出 u=T 的状态即得答案，再叠加状压建模、A* 启发与 -1 预检。luogu P4822[BJWC2012] 冻结B 复用 A 教的“把影响后续的历史维度加进状态、在状态图上跑 Dijkstra”这一步：A 把已用卡数写进 dist[u][used]，B 把已学文化集合写进 (u,mask)，只是把计数维度换成指数位集，再叠加 A 未教的 A* 启发与 -1 预检。

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 图示解析
    3. 正确性
    4. 复杂度
    5. 代码
    6. 实现：A* 启发与 -1 快速判定
  3. 总结

形式化题目

给定 NN 个国家、KK 种文化、MM 条双向道路（边权 dd，可能有重边）。国家 ii 的文化为 CiC_i；使者每到达一个国家就学习当地文化，每种文化最多学一次。另给一个 K×KK\times K 排斥矩阵：aij=1a_{ij}=1 表示「学过文化 ii 的人不能进入文化为 jj 的国家」（注意 aija_{ij} 与 ajia_{ji} 无关，且 i=ji=j 时也排斥）。起点 SS、终点 TT 的文化同样要学。求一条从 SS 到 TT 的合法路径，使边权总和最小；不存在则输出 −1-1。

其中 2⩽N⩽1002\leqslant N\leqslant 100，1⩽K⩽1001\leqslant K\leqslant 100，1⩽M⩽N21\leqslant M\leqslant N^2，1⩽d⩽10001\leqslant d\leqslant 1000。题目背景已声明：本题被证明没有靠谱的多项式做法，测试数据很水。

样例 11：国家 11 文化 11、国家 22 文化 22，且文化 22 排斥文化 11。到国家 22 必先学文化 11，而学过文化 11 的人进不了文化 22 的国家——无解，输出 −1-1。

正解

思路

朴素做法：直接 DFS 枚举所有「文化互异」的简单路径取最短。路径条数是指数级，N=100N=100 时完全跑不动；而且这条路没有可以记忆化的"子问题"——走到同一国家时，路径前缀学过的文化集合不同，后面的可行走法就完全不同。

状态扩充：既然瓶颈是"前缀信息丢了"，就把前缀里真正有影响的部分——已学文化集合——压缩进状态。令状态为 (u,mask)(u, \mathrm{mask})，其中 mask\mathrm{mask} 是一个二进制集合，第 cc 位为 11 表示文化 cc 已经学过。状态 (u,mask)→(v,mask′)(u,\mathrm{mask})\to(v,\mathrm{mask}') 有一条权为 dd 的边，当且仅当原图有边 u→vu\to v 且：

Cv∉mask且aCu,Cv=0C_v \notin \mathrm{mask} \quad\text{且}\quad a_{C_u,C_v}=0

即"文化 vv 没学过"且"当前文化不排斥它"。在这个状态图上从 (S,2CS)(S, 2^{C_S}) 跑 Dijkstra，第一次弹出 u=Tu=T 的状态时，其距离就是答案（进入 TT 时其文化并入集合，符合"到即学"）。

图示解析

用样例 11 看状态图的形状：只有两个国家，但状态有 (1,{1})(1,\{1\})、(2,{2})(2,\{2\})、(2,{1,2})(2,\{1,2\}) 等，状态图与原图结构完全不同：

graph LR
    A["(1, {1}) 起点<br/>学了文化1"]
    B["(2, {2})"]
    C["(2, {1, 2})"]
    A -. "1→2 被拒：a[1][2]=1 且文化2排斥文化1" .-> C
    C -. "进入2不合法" .-> X["无路可达，输出 -1"]

原图上 11 到 22 只有一条边权 1010 的路，但状态图里这条边被文化规则整条删掉：从 (1,{1})(1,\{1\}) 走到国家 22 需要学文化 22，而 a1,2=1a_{1,2}=1（文化 11 排斥文化 22），且终点文化也不可能先学。所以状态图里 (1,{1})(1,\{1\}) 是孤点，最短路不存在，输出 −1-1。这说明为什么不能在原图上直接 Dijkstra——图的"可行边"取决于走到这里时学过什么。

正确性

  • 状态图边权 d⩾1d\geqslant 1 为正，Dijkstra 保证 (u,mask)(u,\mathrm{mask}) 的距离在首次弹出时已最优；TT 的所有合法入口状态里最小者即全局答案。
  • SS、TT 文化计入集合与题面"在起点和终点也会学习当地的文化"一致。

复杂度

状态数最坏 N⋅2KN\cdot 2^K，总复杂度 O(2K⋅Mlog⁡)O(2^K \cdot M \log) 级别——是指数的。这与题目背景"不存在靠谱多项式做法"一致；对 K⩽100K\leqslant 100 的最坏数据并没有多项式算法可救，本题考察的正是给状态补上丢失的信息这一建模思想。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (1LL<<60), BIG = 1000000000LL;
struct Edge{int v; ll d;};
struct State{ll f, dist; int u; string mask; bool operator<(const State& o) const { if(f!=o.f) return f>o.f; return dist>o.dist; }};
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,k,m,s,t; if(!(cin>>n>>k>>m>>s>>t)) return 0; vector<int> culture(n+1); for(int i=1;i<=n;i++) cin>>culture[i]; vector<vector<int> > reject(k+1, vector<int>(k+1)); for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) cin>>reject[i][j]; vector<vector<Edge> > adj(n+1); for(int i=0;i<m;i++){int u,v;ll d;cin>>u>>v>>d; adj[u].push_back({v,d}); adj[v].push_back({u,d});}
    vector<char> seen(n+1); queue<int> bfs; seen[s]=1; bfs.push(s); while(!bfs.empty()){int u=bfs.front();bfs.pop(); for(int i=0;i<(int)adj[u].size();i++){int v=adj[u][i].v; if(!seen[v]){seen[v]=1;bfs.push(v);}}} if(!seen[t]){cout<<-1<<'\n';return 0;}
    bool last=false; for(int w=1;w<=n;w++) if(seen[w]&&culture[w]!=culture[t]&&!reject[culture[w]][culture[t]]) for(int i=0;i<(int)adj[w].size();i++) if(adj[w][i].v==t) last=true; if(!last){cout<<-1<<'\n';return 0;}
    vector<ll> h(n+1,BIG); priority_queue<pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > pq; h[t]=0; pq.push({0,t}); while(!pq.empty()){pair<ll,int> cur=pq.top();pq.pop(); ll du=cur.first; int u=cur.second; if(du>h[u]) continue; for(int i=0;i<(int)adj[u].size();i++){int v=adj[u][i].v; ll nd=du+adj[u][i].d; if(nd<h[v]){h[v]=nd;pq.push({nd,v});}}}
    map<pair<int,string>, ll> best; priority_queue<State> heap; string sm(k+1,'0'); sm[culture[s]]='1'; best[{s,sm}]=0; heap.push({h[s],0,s,sm}); while(!heap.empty()){State cur=heap.top(); heap.pop(); int u=cur.u; string mask=cur.mask; ll dist=cur.dist; pair<int,string> key={u,mask}; if(best[key]<dist) continue; if(u==t){cout<<dist<<'\n';return 0;} for(int i=0;i<(int)adj[u].size();i++){int v=adj[u][i].v; int c=culture[v]; if(mask[c]=='1') continue; if(reject[culture[u]][c]) continue; string nmask=mask; nmask[c]='1'; ll nd=dist+adj[u][i].d; pair<int,string> nk={v,nmask}; if(!best.count(nk)||nd<best[nk]){best[nk]=nd; heap.push({nd+h[v],nd,v,nmask});}} }
    cout<<-1<<'\n'; return 0; }
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 09:55
# update_at: 2026-10-02 09:55

import sys
from heapq import heappop, heappush
from collections import deque

INF = float("inf")
BIG = 10 ** 9  # 启发式不可达哨兵：任何路径长度都小于它


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k, m, s, t = (next(data) for _ in range(5))

    culture = [0] + [next(data) for _ in range(n)]  # 国家 i 的文化（下标从 1 起）
    # reject[i][j] = 1 表示文化 i 排斥文化 j（学过 i 就进不了文化 j 的国家）
    reject = [[0] * (k + 1)] + [[0] + [next(data) for _ in range(k)] for _ in range(k)]

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, d = next(data), next(data), next(data)
        adj[u].append((v, d))
        adj[v].append((u, d))

    seen = [False] * (n + 1)  # 忽略文化的地理连通块（必要条件剪枝用）
    seen[s] = True
    bfs = deque([s])
    while bfs:
        for v, _ in adj[u := bfs.popleft()]:
            if not seen[v]:
                seen[v] = True
                bfs.append(v)
    if not seen[t]:
        print(-1)  # 地理上就不连通，与文化无关
        return

    # 终点的最后一跳是必要条件：必须存在某个可达国家 w 与 t 相邻，
    # 且 c[w]≠c[t]、c[w] 不排斥 c[t]，否则任何路径都无法进入终点。
    last_hop = [
        w
        for w in range(1, n + 1)
        if seen[w] and culture[w] != culture[t] and not reject[culture[w]][culture[t]]
        if any(v == t for v, _ in adj[w])
    ]
    if not last_hop:
        print(-1)
        return

    # A* 启发函数：h[u] = 忽略全部文化限制时 u 到 t 的最短距离，是真实剩余距离的下界。
    h = [BIG] * (n + 1)
    h[t] = 0
    heap = [(0, t)]
    while heap:
        du, u = heappop(heap)
        if du > h[u]:
            continue
        for v, d in adj[u]:
            if du + d < h[v]:
                h[v] = du + d
                heappush(heap, (du + d, v))

    # 状态 = (国家, 已学文化集合 mask)，mask 是 Python 大整数位集；
    # 代价 f = 已走路程 + h[u]（地理下界），按 f 从小到大扩展。
    start_mask = 1 << culture[s]
    best: dict[tuple[int, int], int] = {(s, start_mask): 0}
    heap = [(h[s], 0, s, start_mask)]
    while heap:
        f, dist, u, mask = heappop(heap)
        if u == t:  # 到达终点时终点文化已计入 mask
            print(dist)
            return
        if best.get((u, mask), INF) < dist:
            continue
        for v, d in adj[u]:
            c = culture[v]
            if mask >> c & 1:  # 已学过该文化，不能再进
                continue
            if reject[culture[u]][c]:  # 当前文化排斥 v 的文化
                continue
            nmask = mask | 1 << c
            nd = dist + d
            if best.get((v, nmask), INF) > nd:
                best[(v, nmask)] = nd
                # 启发值可进不可退：f 沿每条边至少加 d，队列按 f 排序不违反 Dijkstra 顺序
                heappush(heap, (nd + h[v], nd, v, nmask))
    print(-1)


if __name__ == "__main__":
    solve()

实现：A* 启发与 -1 快速判定

纯状态 Dijkstra 在最坏数据上会展开海量状态（本题真实数据 culture9 是 N=K=100N=K=100 的大图，答案是 −1-1）。代码里加了两个层面的工程优化：

1. 两条必要条件预检（O(N+M)O(N+M)）——不满足就必无解：

预检 逻辑 依据
地理连通 从 SS 忽略文化 BFS，TT 不可达 → −1-1 任何合法路径都是原图路径
最后一跳 不存在 TT 的邻居 ww（SS 可达）满足 Cw≠CTC_w\neq C_T 且 aCw,CT=0a_{C_w,C_T}=0 → −1-1 路径的最后一步必经某个 TT 的邻居，且该跳必须合法

culture9 恰好是"没有任何邻居能进终点"的构造，预检直接毫秒级返回 −1-1。

2. A* 启发：先在原图上跑一遍忽略文化的 Dijkstra 得 h[u]h[u]（uu 到 TT 的纯地理最短距离）。文化限制只会让路更长或不可行，所以 hh 是真实剩余距离的下界（可采纳）；且 h(v)⩽h(u)+dh(v)\leqslant h(u)+d（一致性），优先队列按 f=g+hf=g+h 弹出时 ff 单调不降，不破坏 Dijkstra 的正确顺序。找到答案前，搜索始终沿"地理上最有希望"的方向扩展，等效于剪掉所有 f\mathrm{f} 超过答案的分支。

对拍式的自证：两个样例与全部 10 组真实测试数据输出一致（包括 −1-1 样例与三组大图）。

总结

  • 本题官方已声明是错题：不存在可靠多项式做法，正解本质是指数状态搜索，考察的是"把路径前缀压缩成 (国家, 已学文化集合)"的状态建模。
  • 在原地图上直接跑最短路是错的：同一国家以不同文化集合到达，后续可行边不同。
  • 两个工程技巧让 Python 也能稳过全部真实数据：必要条件预检快速判 −1-1；忽略文化的地理距离 h[u]h[u] 作 A* 启发（可采纳且一致，保证正确性不变）。
  • 通用教训：当"走过的历史"影响后续决策时，要么把历史的充分信息并入状态，要么用可采纳启发剪枝——单维度最短路模型会静默地给出错误答案。