T3-11 Moving Both Ha

思路解析

问题本质

红球从节点 1 出发，蓝球从节点 i 出发，两球沿有向边移动，目标是找一个汇合点 t，使得：

$$min_t \big(\text{dist}(1 to t) + \text{dist}(i \to t)\big)$$

核心难点

对每个 i（2~n），暴力做法需要跑 n-1 次 Dijkstra，时间不可接受。

建图技巧——分层图

构造一个 2n 个节点的增广图（两层）：

• 第 1 层（节点 1~n）：保留原图的有向边，代表红球的移动。
• 第 2 层（节点 1'~n'，编号 n+1~2n）：将原图所有边反向，代表蓝球的"逆向回溯"。
• 跨层桥边：对每个节点 t，加一条 t → t'（代价 0）的边。

然后从节点 1 跑一次 Dijkstra，到节点 i'（即 i+n）的最短路就是答案。

为什么正确？

从节点 1 出发，在第 1 层走到某个 t，花费 dist(1→t)；然后走桥边到 t'（代价 0）；接着在第 2 层（反向图）从 t' 走到 i'，等价于在原图中从 i 走到 t，花费 dist(i→t)。Dijkstra 自动取所有 t 中的最小值。

---

逐行注释代码

#include <iostream>                        // 引入输入输出流
#include <vector>                          // 引入动态数组 vector
#include <queue>                           // 引入优先队列（用于 Dijkstra）
using namespace std;

typedef long long ll;                      // 用 long long 防止路径权值溢出
typedef pair<ll, int> pli;                 // 存储 (距离, 节点编号) 的二元组

const ll INF = 1e18;                       // 定义无穷大常量
const int MAXN = 400005;                   // 最大节点数（2倍，两层图）

int n, m;                                  // n: 节点数, m: 边数
vector<pair<int, int>> adj[MAXN];          // 邻接表，adj[u] 存 {v, w}
ll dist_arr[MAXN];                         // 存储从起点到每个节点的最短距离

void dijkstra(int s) {                     // Dijkstra 最短路算法，s 为起点
    // 小根堆，按距离从小到大排序
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for (int i = 0; i <= 2 * n; i++)       // 初始化所有距离为无穷大
        dist_arr[i] = INF;
    dist_arr[s] = 0;                       // 起点距离为 0
    pq.push({0, s});                       // 起点入队

    while (!pq.empty()) {                  // 当优先队列不为空时循环
        auto [d, u] = pq.top();            // 取出距离最小的节点
        pq.pop();                          // 弹出堆顶
        if (d > dist_arr[u]) continue;     // 如果是过时的松弛记录，跳过

        for (auto [v, w] : adj[u]) {       // 遍历 u 的所有出边 (v, w)
            if (dist_arr[u] + w < dist_arr[v]) {   // 如果可以松弛
                dist_arr[v] = dist_arr[u] + w;      // 更新最短距离
                pq.push({dist_arr[v], v});           // 将新距离入队
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);           // 关闭同步，加速输入输出
    cin.tie(nullptr);                      // 解除 cin 和 cout 的绑定

    cin >> n >> m;                          // 读入节点数和边数

    for (int i = 0; i < m; i++) {          // 读入 m 条有向边
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});          // 第1层：原图边 u → v，权 w
        adj[v + n].push_back({u + n, w});  // 第2层：反向边 v' → u'，权 w
    }

    for (int t = 1; t <= n; t++) {         // 添加跨层桥边
        adj[t].push_back({t + n, 0});      // 从第1层的 t 到第2层的 t'，代价 0
    }

    dijkstra(1);                           // 从节点 1（红球起点）跑 Dijkstra

    for (int i = 2; i <= n; i++) {         // 输出蓝球起始在 i 时的答案
        if (dist_arr[i + n] >= INF)        // 如果第2层节点 i' 不可达
            cout << -1;                    // 输出 -1，表示无法完成游戏
        else
            cout << dist_arr[i + n];       // 输出到 i' 的最短距离即为答案
        if (i < n) cout << " ";            // 数字之间用空格分隔
    }
    cout << endl;                          // 输出换行
    return 0;                              // 程序结束
}

---