CFR 843 D. Dynamic Shortest Path

Problem Description:
You are given a directed weighted graph with N nodes and M edges. Q queries follow:
OP = 1: Output the shortest path from node 1 to node V.
OP = 2: Read C values, the C[i]'th edge should have its weight incremented by 1.

Constraints:
1 ≤ N, M ≤ 1e5
max weight does not exceed 1e9, initially
sum of C does not exceed 1e6

Solution:
Run Dijkstra's algorithm in the beginning, and we have single source shortest path distance with source from 0 to any node i, denoted as dis[i].
For each operation of the second kind, we want to drop one O(lg) factor, so we would refrain from directly running Dijkstra, that is a waste of previous information. We can drop the O(lg) factor by replacing priority queue to queue when applying Dijkstra's. In order to make this possible, we have to modify the graph we want to run this variant of Dijkstra on, so that its longest shortest path distance does not exceed N. Johnson's algorithm grants us inspiration. We relabel each edge (u -> v) to the current (dis[u] - div[v]) subtracted from its current weight. We can ensure that after relabeling, for every node i, the shortest distance from node 0 to node i is 0. This is apparent because only the potential of the head and the tail nodes are taken into account with this method of relabeling, and the potential difference of node 0 and node i is always dis[i]. In addition to that the shortest distance from node 0 to any node is 0 being ensured, we also know that after each operation of the second kind, the distance increases by no more than C. Hence it is ensured that at most C different distances is of our concern during the update with Dijkstra's.

Code:

#include <bits/stdc++.h>

signed main() {
  std::ios::sync_with_stdio(false);
  int N, M, Q;
  std::cin >> N >> M >> Q;
  std::vector<std::vector<int>> G(N);
  std::vector<std::pair<int, int>> E(M); {
    for (int i = 0; i < M; ++i) {
      int U, V, W;
      std::cin >> U >> V >> W;
      E[i] = std::make_pair(W, V - 1);
      G[U - 1].emplace_back(i);
    }
  };
  std::vector<long long> dis(N, 1LL << 60); {
    std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> pq;
    pq.emplace(dis[0] = 0, 0);
    while (!pq.empty()) {
      long long d;
      int u;
      std::tie(d, u) = pq.top();
      pq.pop();
      if (d != dis[u]) continue;
      for (int ei : G[u]) {
        int w, v;
        std::tie(w, v) = E[ei];
        if (d + w < dis[v]) {
          pq.emplace(dis[v] = d + w, v);
        }
      }
    }
  }
  while (Q--) {
    int OP;
    std::cin >> OP;
    if (OP == 1) {
      int V;
      std::cin >> V;
      if (dis[V - 1] == 1LL << 60) std::cout << -1 << std::endl;
      else std::cout << dis[V - 1] << std::endl;
    } else {
      int C;
      std::cin >> C;
      for (int i = 0; i < C; ++i) {
        int X;
        std::cin >> X;
        ++E[X - 1].first;
      }
      std::vector<int> delta(N, C); {
        std::vector<std::queue<int>> que(C);
        delta[0] = 0;
        que[0].emplace(0);
        for (int i = 0; i < C; ++i) {
          while (!que[i].empty()) {
            int u = que[i].front();
            que[i].pop();
            if (i != delta[u]) continue;
            for (int ei : G[u]) {
              int w, v;
              std::tie(w, v) = E[ei];
              w = std::min<long long>(C, w + dis[u] - dis[v]);
              if (delta[u] + w < delta[v]) {
                que[delta[v] = delta[u] + w].emplace(v);
              }
            }
          }
        }
      }
      for (int i = 0; i < N; ++i) {
        dis[i] = std::min(1LL << 60, dis[i] + delta[i]);
      }
    }
  }
  return 0;
}