「CF843D」Dynamic Shortest Path

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

[CF 843D]

给定 $n$ 个点 $m$ 条边的有向图，边带权。$q$ 个操作，可能是求目前 $1$ 到 $u$ 的最短路或是将 $c$ 条边的权加 $1$。

$n, m\le 10^5, q\le 2000, \sum c\le 10^6$。

主要思路

$q$ 这么小，看起来像是 $O(nq)$。

先跑一遍 Dijkstra 来取得 $\langle dis_i\rangle$，表示 $1$ 到 $i$ 的最短路长度。

每次修改边权， $1$ 到任意其他点的距离比原先都不降。

那么求增量 $\langle f_i\rangle$。设 $e(u, v)$ 表示 $u, v$ 之间连边，$w(u, v)$ 表示 $u, v$ 之间边的边权。

显然对于点 $v$ 有 $f_v = \min\limits_{e(u, v)}(dis_u + f_u + w(u, v) - dis_v)$。

增量有上限 $c$，所以可以直接用桶 $O(n + m)$ bfs 做。

总时间复杂度 $O(n\log n + m + (n + m)q)$。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define FORit(templ, arr, i, a, b) \
for (register templ *i = (arr) + (a), *ed_##i = (arr) + (b) + 1; i != ed_##i; ++i)
#define ROFit(templ, arr, i, a, b) \
for (register templ *i = (arr) + (a), *ed_##i = (arr) + (b)-1; i != ed_##i; --i)
#define GO(x, p, e, i, v) for (register int i = p[x].head, v; i; i = e[i].link)
#define MEM(x, v) memset(x, v, sizeof(x))
#define fir first
#define sec second
#define MP make_pair
typedef long long LL;
typedef double DB;
typedef pair<int, int> PII;
typedef pair<LL, int> PLLI;
#define Templ(T) template <typename T>
inline int read() {
    reg int ans = 0;
    reg char c = getchar();
    while (!isdigit(c)) c = getchar();
    for (; isdigit(c); c = getchar()) ans = (ans << 1) + (ans << 3) + (c ^ 48);
    return ans;
}
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
#define using_mod
const int mod = 998244353;
#ifdef using_mod
inline void inc(int &x, const int &y) { x += y; if (x >= mod) x -= mod; }
inline void dec(int &x, const int &y) { x -= y; if (x < 0) x += mod; }
inline int ksm(int x, LL y) {
    int res = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod)
        if (y & 1) res = 1ll * res * x % mod;
    return res;
}
#endif
Templ(_Tp) inline _Tp gcd(_Tp x, _Tp y) { return y ? gcd(y, x % y) : x; }
#define FILE(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define PBTXDY
} // namespace my_std
using namespace my_std;

const int N = 100010;
#define inf (0x3f3f3f3f3f3f3f3fll)
struct Vertice{
    int head;
}p[N];
struct Edge{
    int link, to, wgh;
}e[N];
LL dis[N], f[N];
int vis[N];
static int ecnt;
inline void A_E(const int &u, const int &v, const int &w){
    e[++ecnt] = (Edge){p[u].head, v, w};
    p[u].head = ecnt;
}
int n, m, q;

priority_queue<PLLI> pq;
inline void dijkstra(){
    memset(dis + 1, 0x3f, sizeof(LL) * n);
    memset(vis + 1, 0, sizeof(int) * n);
    dis[1] = 0;
    pq.push(MP(0, 1));
    Rint u;
    while(!pq.empty()){
        u = pq.top().sec, pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        GO(u, p, e, i, v){
            v = e[i].to;
            if(chkmin(dis[v], dis[u] + e[i].wgh)){
                pq.push(MP(-dis[v], v));
            }
        }
    }
}

queue<int> bar[N];
inline void bfs(const int &cnt){
    memset(f + 1, 0x3f, sizeof(LL) * n);
    f[1] = 0, bar[0].push(1);
    reg LL lim = 0, val = 0;
    while(val <= lim){
        Rint u;
        while(!bar[val].empty()){
            u = bar[val].front(), bar[val].pop();
            if(f[u] < val) continue;
            GO(u, p, e, i, v){
                v = e[i].to;
                if(chkmin(f[v], f[u] + dis[u] - dis[v] + e[i].wgh)){
                    if(f[v] <= cnt){
                        bar[f[v]].push(v);
                        chkmax(lim, f[v]);
                    }
                }
            }
        }
        ++val;
    }
    FOR(i, 2, n) dis[i] = min(dis[i] + f[i], inf);
}

int main(){
    n = read(), m = read(), q = read();
    Rint u, v, w;
    FOR(i, 1, m){
        u = read(), v = read(), w = read();
        A_E(u, v, w);
    }
    dijkstra();
    while(q--){
        u = read();
        if(u == 1){
            v = read();
            printf("%lld\n", dis[v] >= inf ? -1 : dis[v]);
        }
        else{
            v = read();
            FOR(i, 1, v) ++e[read()].wgh;
            bfs(min(v, n - 1));
        }
    }
    return 0;
}