CF843D Dynamic Shortest Path 题解

题意：

有一张 \(n\) 个点 \(m\) 条边的有向带权图，你需要回答如下的 \(q\) 个问题：

1 v 询问以 \(1\) 为起点到 \(v\) 的最短路

2 c l_1 l_2 ... l_c 对于 \(l_1, l_2, \ldots, l_c\) 的边的边权增加 \(1\)。

对于询问2，保证 \(l_i\) 互不相同。

不存在输出 -1。

数据范围：

\(1 \leq n, m \leq 10^5,~1 \leq q \leq 2000,~\sum l_i \le 10^6\)。边权 \(\le 10^9\) ，时限 10s 。

注意到边权虽然很大，但是增量极为有限，这使得我们考察与增量/值域相关的做法。

首先先跑一遍 Dijkstra ，得到每个点的最短路 \(d_u\) ，然后令每条边的新边权为 \[ w(u,v) \gets d_u +w(u,v) - d_v \] 那么此时 \(u \leadsto v\) 的路径的意义就变为了 \(u\) 到 \(v\) 相对于最短路径的增量。

考察 DIjkstra 的过程，每次我们选择 \(d_u\) 最小的 \(u\) 进行拓展。

而现在，整张图的最大权值不会超过 \(10^6\) ，我们就可以用 \(10^6\) 个队列维护每个值当前的 \(u\) 。

然后每次就枚举值域，将当前所有能更新的 \(u\) 取出来尝试松弛，具体详见代码。

实际上，设当前修改了 \(x\) 条边，由于 \(1\) 到每个点的最短路构成一棵树，

而题目保证了 \(l_i\) 互不相同，所以对最短路的增量不会超过 \(\min(x, n - 1)\) ，这样我们只需要 \(10^5\) 个队列即可。

时间复杂度 \(\mathcal{O}(m \log n + \sum l_i)\)

代码：（本题卡常）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3fll
typedef long long ll;
typedef pair<ll, int> pii;
template<typename T> void up(T &x, T y) { x < y ? x = y : (T)0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : (T)0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6 + 15)
    char buf1[SIZ], *p1, *p2;
    char readchar()
    {
        if(p1 == p2) { p1 = buf1, p2 = buf1 + fread(buf1, 1, SIZ, stdin); }
        return p1 == p2? EOF : *p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch = gc(); T x = 0, f = 1;
        while(!isdigit(ch)) { if(ch == '-') { f = -1; } ch = gc(); }
        while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }
        k = x * f;
    }
    template<typename A, typename ...B>
        void read(A &x, B &...y) { return read(x), read(y...); }
    template<typename T>void write(T k)
    {
        if(k < 0){ k = -k; pc('-'); }
        static T stk[66]; T top = 0;
        do{ stk[top++] = k % 10, k /= 10; } while(k);
        while(top) { pc(stk[--top] + '0'); }
    }
}using namespace FastIO;
#define N ((int)(1e5 + 15))
#define Fi first
#define Se second

bool vis[N]; queue<int> q[N];
int n, pos = 1, head[N]; ll d[N], f[N];
struct Edge { int v, w, next; } e[N];
void addEdge(int u, int v, int w) { e[++pos] = {v, w, head[u]}; head[u] = pos; }
void Dijkstra(int s)
{
    static priority_queue<pii> q;
    memset(d, 0x3f, (n + 5) * sizeof(*d));
    d[s] = 0; q.push({0, s});
    while(!q.empty())
    {
        int u = q.top().Se; q.pop();
        if(vis[u]) continue; else vis[u] = true;
        for(int i = head[u]; i; i = e[i].next)
        {
            const int v = e[i].v, w = e[i].w;
            if(d[v] > d[u] + w) { d[v] = d[u] + w; q.push({-d[v], v}); }
        }
    }
}
void bfs(int x)
{
    ll mx = 0;
    for(int now = 0; now <= mx; now++)
    {
        while(!q[now].empty())
        {
            int u = q[now].front(); q[now].pop();
            if(f[u] < now) continue;
            for(int i = head[u]; i; i = e[i].next)
            {
                const int v = e[i].v, w = d[u] + e[i].w - d[v];
                if(f[v] > f[u] + w)
                {
                    f[v] = f[u] + w;
                    if(f[v] <= min(x, n - 1)) { q[f[v]].push(v); up(mx, f[v]); }
                }
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m, qwq; read(n, m, qwq);
    rep(i, 1, m)
    {
        static int u, v, w;
        read(u, v, w); addEdge(u, v, w);
    }
    Dijkstra(1); int op, x, y;
    while(qwq--)
    {
        read(op, x);
        if(op == 1) { write(d[x] == INF ? -1 : d[x]); pc('\n'); }
        else
        {
            rep(i, 1, x) { read(y); ++e[y + 1].w; }
            memset(f, 0x3f, (n + 5) * sizeof(*f));
            f[1] = 0; q[0].push(1);
            bfs(x); rep(i, 1, n) down(d[i] += f[i], INF);
        }
    }
    return 0;
}