T3-17 Dynamic Shorte

思路解析

问题本质

带修改的单源最短路：边权只会递增（+1），需要在修改后高效地更新最短路。

为什么不能暴力重跑 Dijkstra？

• n, m ≤ 10⁵，Dijkstra 一次 O(m log n) ≈ 1.7×10⁶
• q ≤ 2000 次修改，全部重跑：3.4×10⁹，超时

核心技巧：势函数 + Dial 最短路

关键观察：每次修改只是将若干条边权 +1，旧最短路 d[v] 离新最短路 d'[v] 很近。

定义 δ[v] = d'[v] − d[v]（距离增量），可以证明：

任意可达节点 v，δ[v] ≤ n − 1

证明：旧最短路径最多 n−1 条边，其中每条边权最多增加 1，所以旧路径的新代价 ≤ d[v] + (n−1)。新最短路 ≤ 旧路径新代价，故 δ[v] ≤ n−1。

利用势函数将边权缩小：定义缩减权 $r(u,v) = w'(u,v) + d[u] - d[v] \geq 0$

求 δ[v]（从源点出发的缩减权最短路）即可。因为 δ 值有界（≤ n−1），可以用 Dial 算法（桶排序最短路），复杂度 O(n + m) 每次！

总复杂度

步骤	复杂度
初始 Dijkstra	O(m log n)
每次修改后重算	O(n + m)
总计	O(m log n + q·(n + m)) ≈ 4×10⁸ ✓

---

逐行注释代码

#include <cstdio>                          // 使用 scanf/printf 加速 IO
#include <vector>                          // 动态数组
#include <queue>                           // 优先队列（初始 Dijkstra 用）
using namespace std;

typedef long long ll;                      // 长整型，路径长度可达 ~10^14
typedef pair<ll, int> pli;                 // (距离, 节点) 二元组

const ll INF = 1e18;                       // 无穷大
const int MAXN = 100005;                   // 最大节点数

int n, m, q;                               // 节点数、边数、询问数
int eu[MAXN], ev[MAXN];                    // 每条边的起点和终点
ll ew[MAXN];                               // 每条边的当前权值（会动态增加）

vector<pair<int, int>> adj[MAXN];          // 邻接表：adj[u] = {(v, 边编号)}
ll d[MAXN];                                // d[v]: 从 1 到 v 的当前最短距离

// ===================== 初始 Dijkstra =====================
void dijkstra() {
    for (int i = 1; i <= n; i++) d[i] = INF;  // 初始化所有距离为无穷大
    d[1] = 0;                              // 源点距离为 0
    priority_queue<pli, vector<pli>, greater<pli>> pq;  // 小根堆
    pq.push({0, 1});                       // 源点入队

    while (!pq.empty()) {
        auto [dist, u] = pq.top();         // 取出距离最小的节点
        pq.pop();
        if (dist > d[u]) continue;         // 过时状态，跳过

        for (auto& [v, idx] : adj[u]) {    // 遍历 u 的所有出边
            ll nd = d[u] + ew[idx];        // 计算新距离
            if (nd < d[v]) {               // 能松弛
                d[v] = nd;                 // 更新最短距离
                pq.push({nd, v});          // 入队
            }
        }
    }
}

// ===================== Dial 增量更新 =====================
ll delta[MAXN];                            // delta[v] = d'[v] - d[v]，距离增量
bool vis[MAXN];                            // 是否已处理
vector<int> bkt[MAXN];                     // 桶队列：bkt[b] = delta 值为 b 的节点列表

void recompute() {
    for (int i = 1; i <= n; i++) {         // 初始化
        delta[i] = INF;                    // 增量设为无穷大
        vis[i] = false;                    // 标记为未处理
    }
    delta[1] = 0;                          // 源点增量为 0
    bkt[0].push_back(1);                   // 源点放入桶 0

    // Dial 算法：按桶从小到大处理（类似 BFS，但按距离分桶）
    for (int b = 0; b < n; b++) {          // 遍历桶 0 到 n-1
        // 注意：处理桶 b 时可能往桶 b 中添加新节点（r=0 的边）
        // 用下标遍历以动态感知新元素
        for (int idx = 0; idx < (int)bkt[b].size(); idx++) {
            int u = bkt[b][idx];
            if (vis[u]) continue;          // 已处理过，跳过（去重）
            vis[u] = true;                 // 标记为已处理

            for (auto& [v, eidx] : adj[u]) {  // 遍历 u 的所有出边
                if (d[v] >= INF) continue;     // v 不可达，跳过

                // 计算缩减权：r = w'(u,v) + d[u] - d[v]，保证 >= 0
                ll r = ew[eidx] + d[u] - d[v];
                ll nd = delta[u] + r;          // v 的新增量候选值

                if (nd < delta[v]) {           // 能改善 v 的增量
                    delta[v] = nd;             // 更新增量
                    if (nd < n) {              // 增量 < n 才放入桶（已证明最优值 <= n-1）
                        bkt[(int)nd].push_back(v);  // 放入对应桶
                    }
                }
            }
        }
        bkt[b].clear();                    // 处理完后清空桶，为下次 recompute 做准备
    }

    // 用增量更新真实距离
    for (int v = 1; v <= n; v++) {
        if (d[v] < INF && delta[v] < INF) {
            d[v] += delta[v];              // d'[v] = d[v] + delta[v]
        }
    }
}

// ===================== 主程序 =====================
int main() {
    scanf("%d%d%d", &n, &m, &q);           // 读入节点数、边数、询问数

    for (int i = 1; i <= m; i++) {          // 读入 m 条有向边
        scanf("%d%d%lld", &eu[i], &ev[i], &ew[i]);
        adj[eu[i]].push_back({ev[i], i});  // 有向边：从 eu[i] 到 ev[i]
    }

    dijkstra();                            // 初始 Dijkstra，计算所有最短距离

    while (q--) {                          // 处理 q 个询问
        int type;
        scanf("%d", &type);

        if (type == 1) {                   // 查询类型
            int v;
            scanf("%d", &v);
            // 输出最短距离，不可达则输出 -1
            printf("%lld\n", d[v] < INF ? d[v] : -1LL);
        } else {                           // 修改类型
            int c;
            scanf("%d", &c);
            while (c--) {                  // 读入 c 条边编号
                int l;
                scanf("%d", &l);
                ew[l]++;                   // 对应边权值 +1
            }
            recompute();                   // 用 Dial 算法增量更新所有最短距离
        }
    }

    return 0;
}