动态最短路专题

包括删边，删点，修改边权，加边，查询最短路一类问题。

一般图多源最短路

一般图的多源的删边最短路由于受到 Floyd $O(n^3)$ 的限制，做法一般比较单一。

删边，多源最短路

题目
ABC375F Road Blocked

给定一个有 $n$ 个点，$m$ 条边的带权无向图，有 $q$ 个查询，类型如下：

• 1 i：删除第 $i$ 条边；
• 2 x y：求 $x$ 到 $y$ 的最短路长度（无法到达输出 -1）。

数据范围：$n\le 300, m\le \binom n 2$，删边不超过 $300$ 次。

解法
看到删边不超过 $300$ 次启发我们使用 Floyd $O(n^3)$ 解决这个问题。Floyd 能处理新加入一条边，但是比较难做删边，所以我们离线之后倒过来处理，就只需要加边和求任意两点最短路。

怎么用 Floyd 更新一条边对多源最短路的贡献？
假设这条边是 $(u, v)$，长度为 $w$，$d_{i,j}$ 表示 $i,j$ 之间的最短路。
因为更新的最短路只会经过 $(u,v)$ 一次，所以我们用 $d_{i,u}+d_{v,j}+w$ 更新 $d_{i,j}$（反向同理）。

这个更新顺序不会影响答案，因为 $d_{i,u}+d_{v,j}+w$ 的 $d$ 值是不经过 $(u,v)$ 的（因为这条边只会走一次），直接 $O(n^2)$ 处理删边就做完了。

（不难发现这个可以套一个线段树分治，达成 $O(n^2 q\log q )$ 动态删边加边多源最短路，这也引出了下一个问题）

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int N = 305;
ll d[N][N];

struct Edge{int u,v,w;}e[N*N];
bool will_be_deleted[N*N]; // 被删除的边
const int M = 2e5+5;
int op[M][3];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    memset(d,0x3f,sizeof(d));
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }

    for(int i=1;i<=q;i++){
        int o;cin>>o;
        op[i][0]=o;
        if(o==1)cin>>op[i][1],will_be_deleted[op[i][1]]=1;
        else cin>>op[i][1]>>op[i][2];
    }

    for(int i=1;i<=m;i++){
        if(!will_be_deleted[i]){
            d[e[i].u][e[i].v]=d[e[i].v][e[i].u]=e[i].w;
        }
    }

    for(int i=1;i<=n;i++)d[i][i]=0;

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }

    vector<ll> ans;
    for(int x=q;x>0;x--){
        if(op[x][0]==1){
            auto [u,v,w] = e[op[x][1]];
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    d[i][j] = min(d[i][j],d[i][u]+d[v][j]+w);
                    d[i][j] = min(d[i][j],d[i][v]+d[u][j]+w);
                }
            }
        }
        else{
            ans.push_back(d[op[x][1]][op[x][2]]);
        }
    }

    for(auto it=ans.rbegin();it<ans.rend();it++){
        if(*it == d[0][0])*it=-1;
        cout << *it << '\n';
    }
    return 0;
}

删点，多源最短路

题目
QOJ9903 最短路径

给定一个有 $n$ 个点，$m$ 条边的带权有向图，有 $q$ 个查询，输出在删除节点 $p_i$ 的条件下 $s_i$ 到 $t_i$ 的最短路长度，查询删除节点仅对当前查询有效，不持续。

数据范围：$n\le 300, m\le \binom n 2, q\le 5\times 10^5$。

简单版：P1119 灾后重建

解法
我们知道，给定一个无向图，加入一个点更新多源最短路可以 $O(n^2)$ 完成。

因为在 Floyd 中，假设最外层的变量枚举的集合为 $S$，则此时 $d_{i,j}$ 就储存的是原图一个点集 $\{i,j\}\cup S$ 的子图中 $i$ 到 $j$ 的最短路。（从动态规划角度思考）

因此，加点只需要枚举 $i,j$，用 $dp_{i,k}+dp_{k,j}$ 更新 $dp_{i,j}$ 即可。

但是删点就比较困难了，这种能加不能删的问题我们考虑用线段树分治解决。在付出一个 $\log$ 的代价后，我们就不需要考虑删除的问题了。

还需要注意到一个性质，就是删除的节点最多只有 $n$ 种，所以我们可以把删除节点相同的查询放到一起处理（离线），然后直接线段树分治。

这个线段树分治不需要显式地构建出线段树（当然这么写也是可以的），因为叶子 $i$ 是恰好不包含 $i$ 的，所以每次递归的时候，用右子树的每个顶点去更新最短路，得到的结果给左子树，反之亦然。

复杂度 $O(n^3 \log n + q)$。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N = 305;
struct Node{int u,v,id;};
vector<Node> qs[N];
const int Q = 5e5+5;
ll ans[Q];

int n,q;
void solve(int l,int r,vector<vector<ll>> d){
    if(l==r){
        for(auto [u,v,id]:qs[l])ans[id]=d[u][v];
        return;
    }

    auto e = d;
    int mid = (l+r)>>1;
    for(int k=l;k<=mid;k++){
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
            d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
        }
    }
    for(int k=mid+1;k<=r;k++){
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
            e[i][j] = min(e[i][j], e[i][k]+e[k][j]);
        }
    }
    solve(l,mid,e);solve(mid+1,r,d);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>q;
    vector<vector<ll>> d(n+1,vector<ll>(n+1));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> d[i][j];
        }
    }
    for(int i=1;i<=q;i++){
        int s,t,p; cin>>s>>t>>p;
        qs[p].push_back({s,t,i});
    }
    solve(1,n,d);
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
    return 0;
}

一般图单源最短路

删边判断 1 到 n 最短路长度是否变化

题目
ABC375G Road Blocked 2

有一个 $n$ 个点和 $m$ 条边的带权无向图。
对每个 $i \in [1,m]$ 的每一条边，判断删除它之后 $1\to n$ 的最短路长度是否发生变化（若不存在路径，称此时最短路长度为 $-1$）。
数据范围：$n,m \leq 2 \times 10^5$。

解法 1
删除一条边后，最短路长度发生变化的充要条件是：所有最短路都经过它。

• $(\Rightarrow)$：证明它的逆否命题，如果有一条最短路没有经过这条边，最短路长度当然不会变。
• $(\Leftarrow)$：因为所有最短路都经过它，最短路显然会发生变化。

我们用 dijkstra 能轻易计算出 $1\to n$ 有多少条最短路，如果能求出经过一条边的最短路个数就能解决本题。

这也是简单的。分别求出以 $1$ 和 $n$ 为起点的单源最短路，对于一条边 $(u,v,w)$，如果 $1\to u$ 最短路长度，$v\to n$ 最短路长度和 $w$ 加起来为最短路就说明最短路经过这条边，然后只需要把 $1\to u$ 和 $v\to n$ 的最短路方案乘起来就是经过这条边的最短路个数了。（反向经过的也一样计算）

需要套一个哈希，因为最短路径个数很多。

参考代码与题解

解法 2
「我不喜欢哈希，能不能来一个确定性做法？」

我们来考虑另一种做法。
接上文，我们已经把条件转化为了所有最短路都经过这条边。

考虑把所有可能最短路上的边抽出来建立一个子图 $G_0$。
这个命题其实等价于它是这个子图 $G_0$ 的一个割边（桥）。

• $(\Rightarrow)$：证明它的逆否命题，如果不是割边，就存在一条 $1\to n$ 的路径，可以发现子图的任何一条 $1\to n$ 的简单路径长度都是最短路。
• $(\Leftarrow)$：因为是割边，删除后图不连通，假设变成了两个连通块 $S,T$，不妨设 $1\in S$，现在需要证明 $n\in T$ 才能导出这个结论。假设 $n\in S$，则对任意一个 $u\in T$，因为原图存在路径 $1\to u$ 和 $u\to n$，且这两个路径一定不相交，则至少要删掉两条边，矛盾，即证。所以不存在 $1\to n$ 的路径，最短路长度自然改变。

求可能最短路还是从 $1$ 和 $n$ 跑两遍 dijkstra，求割边用 Tarjan 就好了。

参考：连通性问题（2）- 割点和桥。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N = 2e5+5;
struct Edge{int v,w;};
vector<Edge> G[N];

ll d1[N],d2[N];
tuple<int,int,int> edge[N];

bool vis[N];


// s:起点, d: 最短路长度
inline void dijkstra(int s,ll* d){
    memset(vis,0,sizeof(vis));
    priority_queue<pair<ll,int>> pq;
    pq.push({0,s});
    d[s]=0;
    while(pq.size()){
        int u = pq.top().second;pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto [v,w]:G[u]){
            if(d[v] > d[u]+w){
                d[v] = d[u]+w;
                pq.push({-d[v],v});
            }
        }
    }
}

// pair: {v,id}
vector<pair<int,int>> G2[N];
int dfn[N],low[N],tot;
bool is_bridge[N];
void tarjan(int u,int fa){
    dfn[u]=low[u]=++tot;
    for(auto [v,id]:G2[u]){
        if(v==fa)continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])is_bridge[id]=1;
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    memset(d1,0x3f,sizeof(d1));
    memset(d2,0x3f,sizeof(d2));
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        G[u].push_back({v,w});G[v].push_back({u,w});
        edge[i] = {u,v,w};
    }

    dijkstra(1,d1);
    dijkstra(n,d2);

    for(int i=0;i<m;i++){
        auto [u,v,w] = edge[i];
        if(d1[u]+d2[v]+w == d1[n] || d1[v]+d2[u]+w == d1[n]){
            // 在某一条最短路径上，加到子图
            G2[u].push_back({v,i});
            G2[v].push_back({u,i});
        }
    }

    tarjan(1,1);

    for(int i=0;i<m;i++){
        if(is_bridge[i])cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

删边求 1 到 n 最短路长度

是上一题的加强版。

题目
P2685 [TJOI2012] 桥（弱化版：P1186 玛丽卡）

有一个 $n$ 个点和 $m$ 条边的带权无向图。
对每个 $i \in [1,m]$ 的每一条边，判断删除它之后 $1\to n$ 的最短路长度最长是多少，并求出有多少条边能取到这个最大值。
数据范围：$n\le 10^5,m\le 2\times 10^5$，有重边和自环，保证无论删除哪一条边都存在 $1\to n$ 的路径。

解法
先求出 $1\to n$ 的任意一条最短路，如果删除的边不在最短路上显然最短路长度不变（不代表不是最大值）。

成为答案的最短路一定至少经过一条最短路以外的边（除了删除任意边最短路长度都不变的情况，这时候特判），我们枚举这条边。

设 $d1_u$ 表示 $1\to u$ 的最短路长度，$d2_v$ 表示 $v\to n$ 的最短路长度。

对于一条不在最短路上的边 $(u,v,w)$，我们考虑删除最短路上的哪些边时，这条边有可能变成答案。先考虑不删除任何边的时候，强制经过这条边的最短路长度是 $d1_u + d2_v + w$。（反向边也要做，后文所有过程 $(v,u,w)$ 都要再做一次）

如果建出以 $1$ 和 $n$ 为根的任意两颗最短路树（但是强制包含我们钦定的那条最短路，这是可以做到的）。

考察上文长度为 $d1_u + d2_v + w$ 的路径，除了经过这条边，还经过两段 $1\to u$ 和 $v\to n$ 的路径，$1\to u$ 的最短路和我们钦定的最短路有一段公共前缀，$v\to n$ 的最短路有一段公共后缀。

记 $l_u$ 表示 $1\to n$ 的最短路径上第一条不在最短路树上 $1\to u$ 最短路径的边（也就是公共前缀的后一个），$r_u$ 表示 $1\to n$ 的最短路径上最后一条不在另一颗最短路树上 $v\to n$ 的边。

如果删除的边在 $[l_u,r_v]$ 之间，那么我们发现包括 $(u,v,w)$ 的那条最短路完全没有受到影响，因此用 $d1_u + d2_v + w$ 更新删除 $[l_u,r_v]$ 的可能最短路长度。（取所有更新过的最小值）

接下来还要证明如果删除的边在 $[l_u,r_v]$ 之外，一定有一条最短路不经过 $(u,v,w)$，我们就可以用线段树做一个区间取最小值解决本题了。（因为所有有可能经过 $(u,v,w)$ 的最短路我们都更新到了）

这个结论是对的。假设删除的边在 $[l_u,r_v]$ 之外，存在一条最短路 $1\to u \to v \to n$。如果 $r_u \ge l_u -1$，那么 $1\to u$ 后面可以直接连到 $u\to n$ 不经过其他非树边。如果 $r_u < l_u -1$，那么这种情况是不存在的。画图就可以知道没有这样子的最短路树。

所以做完了。复杂度 $O(m\log m)$。

注意如果最后线段树的最大值和原最短路一样，那么可能删除的边应该是 $m$ 而不是 $1\to n$ 的最短路经过边数，因为这时候删除非最短路边也会达到最值。

在实现细节方面可以注意两点：

1. 事实上，这问题需要的数据结构是区间取最小值，单点查询（先全部修改再全部查询），可以扫描一遍用 multiset 解决，会更好写一点。
2. 有关这两颗最短路树的构建，因为已知一条 $1\to n$ 的链，可以从这个链上的每一个点出发 bfs（不能经过这条链上的点），这样搜索到的节点在最短路树上的 LCA 就是当前节点，就能方便求出 l 和 r 数组，同时也保证了最短路树包含了我们的最短路。

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5+5;
vector<tuple<int,int,int>> G[N];
tuple<int,int,int> edges[N];
int d1[N],d2[N];
bool vis[N];

void dijkstra(int s,int* d){
    memset(d,0x3f,N*sizeof(int));
    memset(vis,0,sizeof(vis));
    priority_queue<pair<int,int>> pq;
    pq.push({0,s});
    d[s]=0;
    while(pq.size()){
        int u = pq.top().second;pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto [v,w,_]:G[u])
            if(d[v] > d[u]+w) d[v]=d[u]+w, pq.push({-d[v],v});
    }
}

int l[N],r[N];
// in_path：点是否在最短路中，used:边是否在最短路中
bool in_path[N],used[N]; 

void bfs(int s,int val, int* d,int* arr){
    queue<int> q;q.push(s);
    while(q.size()){
        int u = q.front(); q.pop();
        arr[u] = val;
        for(auto [v,w,id]:G[u]){
            if(in_path[v] || arr[v])continue;
            if(d[v]==d[u]+w)q.push(v);
        }
    }
}

vector<int> add[N],del[N]; 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w; cin>>u>>v>>w;
        edges[i]={u,v,w};
        G[u].push_back({v,w,i});G[v].push_back({u,w,i});
    }
    dijkstra(1,d1); dijkstra(n,d2);
    vector<int> path = {1};  // 一条最短路
    int now = 1; in_path[1] = 1;
    while(now != n){
        for(auto [v,w,id]:G[now]){
            if(d1[now] + d2[v] + w == d1[n]){ // now->v 在最短路上
                now = v; path.push_back(v);
                in_path[now] = 1; used[id] = 1;
                break;
            }
        }
    }

    // l,r 数组存储的是边的编号，从 1~path.size()-1
    for(int i=0;i<path.size();i++)bfs(path[i], i+1, d1, l);
    for(int i=path.size()-1;i>=0;i--)bfs(path[i], i, d2, r);

    for(int i=1;i<=m;i++){
        if(used[i])continue; // 这条边在最短路上，不算它
        auto [u,v,w] = edges[i];
        if(l[u]<=r[v]){
            add[l[u]].push_back(d1[u]+d2[v]+w);
            del[r[v]+1].push_back(d1[u]+d2[v]+w);
        }
        swap(u,v);
        if(l[u]<=r[v]){
            add[l[u]].push_back(d1[u]+d2[v]+w);
            del[r[v]+1].push_back(d1[u]+d2[v]+w);
        }
    }

    int minv = 0, mincnt = 0; 
    multiset<int> val;
    for(int i=1;i<path.size();i++){
        for(auto x:add[i])val.insert(x);
        for(auto x:del[i])val.erase(val.find(x));
        int v = *val.begin();
        if(v>minv)minv=v,mincnt=1;
        else if(v==minv)++mincnt;
    }

    if(minv == d1[n])mincnt = m;
    cout << minv << ' ' << mincnt << '\n';
    return 0;
}

改一条边权查询 1 到 n 最短路

题目
CF1163F. Indecisive Taxi Fee
有一个 $n$ 个点和 $m$ 条边的带权无向图。
查询把第 $i$ 条边边权改成 $j$ 后，$1$ 到 $n$ 的最短路长度，查询之间独立。
数据范围：$n,m,q\le 2\times 10^5$。

解法
是上一题的加强版，因此请先确定你会上一题再来完成本题。
两题思路并没有明显区别，做法也很相似。

延续上一问的做法，随便找到一条最短路，以及 $l_u, r_u$，分别表示 $1\to n$ 的最短路径上第一条不在最短路树上 $1\to u$ 最短路径的边（也就是公共前缀的后一个）和 $1\to n$ 的最短路径上最后一条不在另一颗最短路树上 $v\to n$ 的边。

设 $d1_u$ 表示在原图上 $1\to u$ 的最短路长度，$d2_v$ 表示 $v\to n$ 的最短路长度。

分类讨论修改的边：

1. 修改的边不在最短路径上：
   最短路取 $d1_u + d2_v + w$ 和 $d1_n$ 的最小值。
2. 修改的变在最短路径上：
   求把这条边断掉求最短路，和原最短路修改之后的较小值。删边最短路已经在上一题中很详细的阐述了，用线段树或 multiset 即可。（注意这道题 multiset 可能是空的，此时应采用 $\infty$）

注意：这道题没有保证整个图连通，所以对于不和 $1,n$ 连通的些边应该忽视。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


const int N = 2e5+5;
vector<tuple<int,int,int>> G[N];
tuple<int,int,int> edges[N];
ll d1[N],d2[N];
bool vis[N];

void dijkstra(int s,ll* d){
    memset(d,0x3f,N*sizeof(ll));
    memset(vis,0,sizeof(vis));
    priority_queue<pair<ll,int>> pq;
    pq.push({0,s});
    d[s]=0;
    while(pq.size()){
        int u = pq.top().second;pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto [v,w,_]:G[u])
            if(d[v] > d[u]+w) d[v]=d[u]+w, pq.push({-d[v],v});
    }
}

int l[N],r[N];
// in_path：点是否在最短路中， edge_id:边是否在最短路中的编号
bool in_path[N];
int edge_id[N]; 

void bfs(int s,int val, ll* d,int* arr){
    queue<int> q;q.push(s);
    while(q.size()){
        int u = q.front(); q.pop();
        arr[u] = val;
        for(auto [v,w,id]:G[u]){
            if(in_path[v] || ~arr[v])continue;
            if(d[v]==d[u]+w)q.push(v);
        }
    }
}

vector<ll> add[N],del[N]; 
ll cutd[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,q; cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v,w; cin>>u>>v>>w;
        edges[i]={u,v,w};
        G[u].push_back({v,w,i});G[v].push_back({u,w,i});
    }
    dijkstra(1,d1); dijkstra(n,d2);
    vector<int> path = {1};  // 一条最短路
    int now = 1; in_path[1] = 1;
    while(now != n){
        for(auto [v,w,id]:G[now]){
            if(d1[now] + d2[v] + w == d1[n]){ // now->v 在最短路上
                edge_id[id] = path.size();
                now = v; path.push_back(v);
                in_path[now] = 1; 
                break;
            }
        }
    }

    // 如果l,r没有被修改，那么说明这个节点根本不和1->n所在连通块连通
    memset(l,-1,sizeof(l));memset(r,-1,sizeof(r));

    // l,r 数组存储的是边的编号，从 1~path.size()-1
    for(int i=0;i<path.size();i++)bfs(path[i], i+1, d1, l);
    for(int i=path.size()-1;i>=0;i--)bfs(path[i], i, d2, r);

    for(int i=1;i<=m;i++){
        if(edge_id[i])continue; // 这条边在最短路上，不算它
        auto [u,v,w] = edges[i];
        if(!~l[u])continue; // 不连通，不算他。

        if(l[u]<=r[v]){
            add[l[u]].push_back(d1[u]+d2[v]+w);
            del[r[v]+1].push_back(d1[u]+d2[v]+w);
        }
        swap(u,v);
        if(l[u]<=r[v]){
            add[l[u]].push_back(d1[u]+d2[v]+w);
            del[r[v]+1].push_back(d1[u]+d2[v]+w);
        }
    }

    multiset<ll> val;
    for(int i=1;i<path.size();i++){
        for(auto x:add[i])val.insert(x);
        for(auto x:del[i])val.erase(val.find(x));
        cutd[i] = val.size() ? *val.begin() : LLONG_MAX;
    }

    while(q--){
        int t,new_w; cin>>t>>new_w;
        auto [u,v,w] = edges[t];
        if(!~l[u])cout<<d1[n]<<'\n'; // u -> v 和 n 没有关系，不带他玩。
        else if(edge_id[t])cout << min(cutd[edge_id[t]],d1[n] + new_w - w) << '\n';
        else cout << min({d1[v]+d2[u]+new_w,d1[u]+d2[v]+new_w, d1[n]}) << '\n';
    }

    return 0;
}

多次边权加 1，查询 1 到 u 最短路

题目
CF843D. Dynamic Shortest Path
有一个 $n$ 个点和 $m$ 条边的带权有向图。

支持两种操作：

1. 给出 $c$ 条边，将它们的边权加 $1$。
2. 求 $1\to u$ 的最短路，如果不存在输出 -1。

数据范围：$n,m\le 1\times 10^5,q\le 2000,\sum{c}\le 10^6$。

解法

我们先介绍引入势能的最短路。（和在 Johnson 全源最短路里的势能是一样的）

给图上每一个点赋势能 $h_u$，将所有从 $u\to v$ 的边边权从 $w$ 变为 $w+h_u-h_v$，然后在新图上从 $1$ 开始跑最短路。可以证明，无论势能怎么取，新图上的最短路距离总满足 $d'_u = d_u + h_1 -h_u$（考虑势能抵消），于是就可以用新图的最短路来求出原图的最短路。

现在我们有 $c$ 条边需要边权加 $1$。如果我们用加 $1$ 之前的最短路距离 $d_{0 u}$ 作为点 $u$ 的势能，我们能发现一些关键性质：

1. 任何新图的边权非负，因为 $w+h_u-h_v\ge w_0 + h_u - h_v$，而 $d_{0v}\le d_{0u}+w_0$，得证。于是可以用 dijkstra 来求最短路。
2. 新图的最短路最大值为 $\min(c,n-1)$，因为考虑原图的最短路树，最短路树上的边边权最多为 $1$，所以最短路的上界是 $n-1$，而只加了 $c$ 条边最短路最多增加 $c$。

因此，只要在 $O(n+m+W)$ 解决最短路最大值为 $W$ 图的 dijkstra 就可以在 $O(q(n+m) + m\log m)$ 的复杂度内解决本题（对于每个操作 1 都跑一遍 dijkstra 更新最短路，然后 $O(1)$ 回答操作 2）。
这是很容易做到的。普通 dijkstra 的瓶颈在于优先队列的 $\log$，因为值域很小，我们可以用一个桶来代替优先队列，每次从桶内取出元素即可。

有点卡常，如果你要写建议小心一点。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1e5+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
pair<int,int> edges[N];
int head[N],nxt[N],tot;
void add_edge(int u){
    ++tot;
    nxt[tot]=head[u];
    head[u]=tot;
}

// O(m log m)
void dijkstra(int s,ll* d){
    bitset<N> vis;
    memset(d,0x3f,N*sizeof(*d));
    priority_queue<pair<ll,int>> pq;
    pq.push({0,s});
    d[s]=0;
    while(pq.size()){
        int u = pq.top().second;pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int o=head[u];o;o=nxt[o]){
            auto [v,w] = edges[o];
            if(d[v] > d[u]+w) d[v]=d[u]+w, pq.push({-d[v],v});
        }
    }
}

queue<int> buc[N];
// 带势能 dijkstra，O(n+m), mx:最短路的一个上界，h: 势能, d:最短路
void dijkstra_with_bucket(int s,int mx,const ll *h,int *d){
    memset(d,0x3f,N*sizeof(*d));
    d[s]=0; buc[0].push(s);
    for(int i=0;i<=mx;i++){
        while(buc[i].size()){
            auto u = buc[i].front(); buc[i].pop();
            if(d[u] < i)continue;
            for(int o=head[u];o;o=nxt[o]){
                auto [v,w] = edges[o];
                ll wh = h[u]-h[v]+w;  // 为什么不用 h[v]-h[u]？因为这样会导致边权可能是负的。
                if(d[u]+wh<min(mx+1,d[v]))d[v]=d[u]+wh,buc[d[v]].push(v);
            }
        }
    }
}

ll d[N];int newd[N];
int main(){    
    int n=read(),m=read(),q=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add_edge(u);
        edges[i]={v,w};
    }
    dijkstra(1,d);
    while(q--){
        int op=read();
        if(op==1){
            int u=read();
            cout << (d[u]==INF?-1:d[u]) << '\n';
        }
        else{
            int cnt=read(), mx = min(cnt, n-1);
            while(cnt--)edges[read()].second++;
            dijkstra_with_bucket(1, mx, d, newd);
            for(int i=1;i<=n;i++)d[i]+=(d[i]==INF?0:newd[i]); 
        }
    }
    return 0;
}

有限制图的多源最短路

一般图显然是不可做的（因为不弱于静态多源最短路 $O(n^3)$ 或 $O(nm \log m)$）。但是如果图有一些特殊的性质（比如是树/基环树），这个问题还是可以完成的。

基环树的动态多源最短路

题目
P4949 最短距离
给出一个 $n$ 个点 $n$ 条边的带权无向连通图，支持 $q$ 次操作，每次为两种之一：

1. 修改第 $x$ 条边的长度为 $y$；
2. 查询点 $x$ 到点 $y$ 的最短距离。

数据范围：$n\le 10^5+6,m\le 10^5$。

解法
原图是一个基环树。

基环树有两种处理方法：

1. 看作是一个环，环上每一个点都挂了一棵树；
2. 看作一棵树多一条边。

本题这两种做法都可以，此处提供更好写的第 2 种方法，有关方法 1 可以查看原题的题解区。

假设是一棵树和额外的边 $(u,v,w)$。
从节点 $x\to y$ 一共有三种情况：

• 从树上 $x\to y$；
• 从树上 $x\to u$，经过 $(u,v,w)$ 再从树上 $v\to y$；
• 从树上 $x\to v$，经过 $(v,u,w)$ 再从树上 $u\to y$。

问题就转化成：修改树的边权，求树上两点路径距离。

这是经典的树链剖分，可以 $O(\log^2 n)$ 完成，我们再介绍一个单 $\log$ 的写法。

先把边权下放到点。我们要做的是修改点权，查询路径上除 LCA 的点权和。做一个树上前缀和，$d_i$ 表示 $i$ 到根的点权和，修改就是一个子树加，查询是 $d_u+d_v-2d_{\operatorname{LCA}(u,v)}$，可以树状数组维护。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N = 1e5+10;
int dep[N],dfn[N],sz[N],tot,fa[N][20];
vector<pair<int,int>> G[N];

// 每条边下端所对应的节点，0表示不在树上
int low[N],ex_id;
tuple<int,int,int> edges[N];

void dfs(int u,int f){
    dep[u] = dep[f] + 1;
    sz[u] = 1; dfn[u] = ++tot;
    fa[u][0] = f;
    for(int i=1;i<=__lg(dep[u]);i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(auto [v,id]:G[u]){
        if(v==f)continue;
        dfs(v,u);low[id]=v;
        sz[u]+=sz[v];
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    while(dep[u]<dep[v])v = fa[v][__lg(dep[v]-dep[u])];
    if(u==v)return u;
    for(int i=__lg(dep[u]);i>=0;i--){
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}

struct DSU{
    int fa[N];
    void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    void unite(int i,int j){fa[find(i)]=find(j);}
}dsu;

int n,q;
struct BIT{
    ll t[N];
    void add(int x,ll v){
        if(!x)return; // 忽略 x = 0
        for(;x<=n;x+=x&-x)t[x]+=v;
    }
    ll query(int x){
        ll ans = 0;
        for(;x;x-=x&-x)ans+=t[x];
        return ans;
    }

    void add_u(int u,int x){
        add(dfn[u],x);
        add(dfn[u]+sz[u],-x);
    }
    ll query_path(int u,int v){
        int w = lca(u,v);
        return query(dfn[u])+query(dfn[v])-2*query(dfn[w]);
    }
}bit;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>n>>q;
    dsu.init(n);
    for(int i=1;i<=n;i++){
        int u,v,w;cin>>u>>v>>w;
        edges[i]={u,v,w};
        if(dsu.find(u)==dsu.find(v))ex_id = i;
        else{
            dsu.unite(u,v);
            G[u].push_back({v,i});G[v].push_back({u,i});
        }
    }

    dfs(1,0);
    for(int i=1;i<=n;i++){
        auto [u,v,w] = edges[i];
        if(low[i])bit.add_u(low[i], w);
    }

    while(q--){
        int op,x,y; cin>>op>>x>>y;
        if(op==1){
            auto& [u,v,w] = edges[x];
            if(low[x])bit.add_u(low[x],y-w);
            w=y;
        }
        else{
            auto [eu,ev,ew] = edges[ex_id];
            int ans = min({
                bit.query_path(x,y),
                bit.query_path(x,eu)+ew+bit.query_path(ev,y),
                bit.query_path(x,ev)+ew+bit.query_path(eu,y),
            });
            cout << ans << '\n';
        }
    }
    return 0;
}

CF838B Diverging Directions

题目
CF838B Diverging Directions
给出一个 $n$ 个点 $2n-2$ 条边的带权有向图，图的结构为：

• 前 $n-1$ 条边构成一个以 $1$ 为根的外向树；
• 后 $n-1$ 条边是 $i\ (2\le i \le n)$ 连向 $1$ 的有向边。

你需要支持 $q$ 次操作，每次为两种之一：

1. 修改第 $x$ 条边的长度为 $y$；
2. 查询点 $x$ 到点 $y$ 的最短距离。

数据范围：$n,q\le 2\times 10^5$。

解法

求 $x\to y$ 的最短路。

1. 如果在树上 $x$ 是 $y$ 的祖先，那么从 $x$ 一路往下到 $y$ 就是最优解。
2. 否则，可以证明最短路一定是 $x$ 往下走一段（可以不走），然后用第二类边回到 $1$，最后一直往下到 $y$。

设 $d1_u$ 表示树上 $1\to u$ 的边权和，$d2_u$ 表示 $u\to 1$ 的边权。

对于修改，修改第一类边边权就是子树 $d1$ 加，修改第二类边边权就是单点 $d2$ 加。

第一种最短路的边权就可以写作 $d1_y-d1_x$，容易解决。
第二种最短路的边权是 $\min_{v} \{d1_v-d1_x+d2_v+d1_y\}$（$v$ 是 $u$ 的后代）。$d1_y-d1_x$ 是定值，分离出来，就要求子树内 $d1_v+d2_v$ 最小值，用区间加，区间最小值线段树解决。

还需要求 LCA，选择喜欢的方法即可。（后面代码是倍增）

复杂度 $O((n + q)\log n)$。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int N = 2e5+5;

ll d1[N],d2[N]; 
vector<pair<int,int>> G[N];
int dfn[N],id[N],sz[N],tot,dep[N],fa[N][20];
void dfs(int u,int f){
    dep[u] = dep[f] + 1;
    dfn[u]=++tot;id[tot]=u;sz[u]=1;
    fa[u][0] = f;
    for(int i=1;i<=__lg(dep[u]);i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(auto [v,w]:G[u]){
        d1[v]=d1[u]+w;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    while(dep[u]<dep[v])v = fa[v][__lg(dep[v]-dep[u])];
    if(u==v)return u;
    for(int i=__lg(dep[u]);i>=0;i--){
        if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}

// 区间加，区间min
ll t[N*4],tag[N*4];
void build(int o,int l,int r){
    if(l==r){
        t[o] = d1[id[l]]+d2[id[l]];
        return;
    }
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    build(lch,l,mid);build(rch,mid+1,r);
    t[o]=min(t[lch],t[rch]);
}
void add(int o,ll k){
    t[o] +=k; tag[o]+=k;
}
void pushdown(int o){
    if(tag[o]){
        int lch=o<<1,rch=o<<1|1;
        add(lch,tag[o]),add(rch,tag[o]);
        tag[o]=0;
    }
}
void modify(int o,int l,int r,int ql,int qr,ll k){
    if(ql<=l&&r<=qr)return add(o,k);
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    pushdown(o);
    if(ql<=mid)modify(lch,l,mid,ql,qr,k);
    if(qr>mid) modify(rch,mid+1,r,ql,qr,k);
    t[o]=min(t[lch],t[rch]);
}
ll query(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return t[o];
    int lch=o<<1,rch=o<<1|1;
    int mid=(l+r)>>1;
    pushdown(o);
    if(qr<=mid)return query(lch,l,mid,ql,qr);
    if(ql>mid) return query(rch,mid+1,r,ql,qr);
    return min(query(lch,l,mid,ql,qr),query(rch,mid+1,r,ql,qr));
}

struct Edge{
    int u,v,w;
}edges[N*2];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cout<<fixed;

    int n,q; cin>>n>>q;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w;
        edges[i]={u,v,w};
        G[u].push_back({v,w});
    }
    for(int i=n;i<=2*n-2;i++){
        int u,v,w; cin>>u>>v>>w;
        edges[i]={u,v,w};
        d2[u]=w;
    }

    dfs(1,1);
    
    build(1,1,n);

    while(q--){
        int op,x,y; cin>>op>>x>>y;
        if(op==1){
            if(x<=n-1){
                auto &[_,u,w] = edges[x];
                modify(1,1,n,dfn[u],dfn[u]+sz[u]-1,y-w);
                w=y;
            }
            else{
                auto &[u,_,w] = edges[x];
                modify(1,1,n,dfn[u],dfn[u],y-w);
                w=y;d2[u]=w;
            }
        }
        else{
            ll d1x = query(1,1,n,dfn[x],dfn[x])-d2[x];
            ll d1y = query(1,1,n,dfn[y],dfn[y])-d2[y];
            if(lca(x,y)==x){
                cout << d1y - d1x << '\n';
            }
            else{
                cout << d1y + query(1,1,n,dfn[x],dfn[x]+sz[x]-1) - d1x << '\n';
            }
        }
    }
    return 0;
}