题解：CF843D Dynamic Shortest Path

https://www.luogu.com.cn/problem/CF843D

luogu RMJ 加油.......

如果每修改一次就 dij 复杂度 \(O(q (n + m \log n))\) 过不去的。

暴力 dij 是因为值域很大需要用到堆，带个 log，要是值域很小就可以直接分层 BFS 了……

每次增加的边权很小，求最短路增量？设 \(dis_i\) 表示这次修改前最短路，\(f_i\) 表示这次修改后最短路增量。

有 \(f_v = \min\limits_{(u,v) \in E}{dis_u + f_u + w(u,v) - dis_v}\)。

而每次修改后最大增量是小于等于 \(c\) 的，可以分层 BFS。

注意每一层可能由自己这一层转移来（因为边权为 0），所以每一层内部需要用队列。

复杂度 \(O(q(c + m + n))\)。

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXN = 1e5 + 3;

struct Edge{ // 链式前向星 方便修改边权
  int to, epre, w;
}eg[MAXN];
int egtop[MAXN], tot = 0;

int ADDeg(int u, int v, int val){
  tot++, eg[tot].to = v, eg[tot].w = val;
  eg[tot].epre = egtop[u], egtop[u] = tot;
  return tot;
}

int n, m, Q, id[MAXN];
LL dis[MAXN], f[MAXN];
queue<int> p[MAXN];

void dij(){
  for(int i = 1; i <= n; i++){
    dis[i] = 1e18;
  }
  priority_queue<pair<LL, int>> pq;
  dis[1] = 0, pq.push({0, 1});
  while(!pq.empty()){
    pair<LL, int> w = pq.top();
    int i = w.second;
    pq.pop();
    if(dis[i] < -w.first) continue;
    for(int e = egtop[i]; e > 0; e = eg[e].epre){
      int nx = eg[e].to;
      LL nw = dis[i] + eg[e].w;
      if(dis[nx] > nw) dis[nx] = nw, pq.push({-nw, nx});
    }
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0); 
  cin >> n >> m >> Q;
  for(int i = 1, U, V, W; i <= m; i++){
    cin >> U >> V >> W, id[i] = ADDeg(U, V, W);
  }
  dij();
  for(int q = 1, op, c, v; q <= Q; q++){
    cin >> op >> c;
    if(op == 1){
      cout << (dis[c] >= 1e18 ? -1 : dis[c]) << "\n";
    }else{
      for(int _c = 0; _c < c; _c++){
        cin >> v, eg[id[v]].w++;
      }
      for(int i = 1; i <= n; i++) f[i] = c + 1;
      f[1] = 0, p[0].push(1);
      for(int d = 0; d <= c; d++){
        while(!p[d].empty()){
          int x = p[d].front();
          p[d].pop();
          if(f[x] < d) continue;
          for(int e = egtop[x]; e > 0; e = eg[e].epre){
            int nx = eg[e].to;
            LL nw = dis[x] + f[x] + eg[e].w - dis[nx];
            if(nw < f[nx]) f[nx] = nw, p[nw].push(nx);
          }
        }
      }
      for(int i = 1; i <= n; i++) dis[i] += f[i];
      for(int d = 0; d <= c; d++){
        while(!p[d].empty()) p[d].pop();
      }
    }
  }
  return 0; 
}