题解：葡萄藤上的百合花

题目大意

• 有 $n = 2^k$ 个节点（编号 $0 \dots 2^k-1$）
• 两种移动方式：
  1. 葡萄藤边：$m$ 条双向边 $(x_i, y_i, c_i)$
  2. 闪现：任意两点 $u, v$ 之间可花费 $a_t$ 时间移动，其中 $t = \text{popcount}(u \oplus v)$
• 求从起点 $s$ 到所有节点的最短时间

数据范围：$k \leq 17, m \leq 2\times 10^5$

---

问题分析

直接建图不可行，因为闪现边数量为 $O(n^2)$，会爆炸。

关键观察：闪现边的权值只依赖于两个节点的异或值（汉明距离）。

---

核心思路

设 $d[x]$ 表示从 $s$ 到 $x$ 的最短时间。

1. 葡萄藤边处理

直接作为普通边在 Dijkstra 中更新。

2. 闪现边处理

对于任意点 $u$，闪现到 $v = u \oplus mask$ 的花费是 $a_{\text{popcount}(mask)}$。

我们定义：

$$w[mask] = a_{\text{popcount}(mask)}$$

那么闪现更新可以表示为：

$$d[v] = \min(d[v], d[u] + w[u \oplus v])$$

但枚举所有 $(u, v)$ 不可行。

---

高效算法：分层更新

我们可以定期执行一次 全局闪现更新：

$$d'[x] = \min_{y} \{ d[y] + w[x \oplus y] \}$$

这等价于对 $d$ 和 $w$ 进行 最小值卷积：

$$d' = d \ast w \quad \text{其中} \quad (f \ast g)[x] = \min_y \{ f[y] + g[x \oplus y] \} $$

这种卷积可以用 快速沃尔什变换（FWT） 的最小值版本在 $O(k \cdot 2^k)$ 时间内完成。

---

算法步骤

1. 初始化

   • $d[s] = 0$，其他 $d[i] = \infty$
   • $w[mask] = a_{\text{popcount}(mask)}$（注意 $w[0] = 0$）

2. Dijkstra 主循环

   • 从优先队列取出 $d[u]$ 最小的 $u$
   • 用葡萄藤边更新邻居
   • 如果当前轮次需要全局更新，执行一次最小值卷积更新 $d$

3. 输出 $d[0 \dots 2^k-1]$

---

复杂度分析

• 葡萄藤边更新：$O(m \log n)$
• 全局闪现更新：$O(k \cdot 2^k)$
• 总复杂度：$O(m \log n + k \cdot 2^k)$，可以接受

---

代码实现要点

// 伪代码
void solve() {
    vector<long long> d(n, INF);
    vector<long long> w(n);
    
    // 初始化 w
    for (int mask = 0; mask < n; mask++) {
        w[mask] = a[__builtin_popcount(mask)];
    }
    w[0] = 0;  // 自己到自己的花费为0
    
    d[s] = 0;
    priority_queue<pair<long long, int>> pq;
    pq.push({0, s});
    
    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (dist != d[u]) continue;
        
        // 葡萄藤边更新
        for (auto [v, cost] : graph[u]) {
            if (d[v] > d[u] + cost) {
                d[v] = d[u] + cost;
                pq.push({d[v], v});
            }
        }
        
        // 全局闪现更新（可以每几次迭代执行一次）
        vector<long long> new_d = d;
        for (int i = 0; i < k; i++) {
            for (int mask = 0; mask < n; mask++) {
                if (mask >> i & 1) {
                    new_d[mask] = min(new_d[mask], new_d[mask ^ (1 << i)] + w[1 << i]);
                }
            }
        }
        // 需要多次迭代确保完全更新
        for (int i = 0; i < k; i++) {
            for (int mask = 0; mask < n; mask++) {
                if (mask >> i & 1) {
                    new_d[mask] = min(new_d[mask], new_d[mask ^ (1 << i)] + w[1 << i]);
                }
            }
        }
        
        // 更新 d 和优先队列
        for (int i = 0; i < n; i++) {
            if (new_d[i] < d[i]) {
                d[i] = new_d[i];
                pq.push({d[i], i});
            }
        }
    }
    
    // 输出答案
    for (int i = 0; i < n; i++) {
        cout << d[i] << " ";
    }
}

---

样例解释

输入：

3 6 2
17 14 11
0 2 3
4 2 9
2 2 1
2 2 6
7 0 5
4 2 9

输出：

3 14 0 17 9 11 17 8

• $d[2] = 0$（起点）
• $d[0] = 3$（通过边 0-2）
• $d[4] = 9$（通过边 4-2）
• 其他点通过闪现或组合路径到达

---

总结

本题的关键在于：

1. 认识到闪现边权值只依赖于汉明距离
2. 使用最小值卷积批量处理闪现更新
3. 结合 Dijkstra 处理稀疏的葡萄藤边

这种 图论 + 状态压缩 + 卷积优化 的思路在处理大规模隐式图时非常有用。