cf1163f

假设不经过边 $t$ 的最短路为 $D_t$，经过的为 $B_t$，那么答案显然为 $\min(D_t,B_t-w_t+x)$。我们只要对每条边把这两者求出来即可。 dij 求出 $1\to n$ 的任意一条最短路 $p_{1\sim s}$，如果 $t$ 不在其上的话，显然必有 $D_t=\mathrm{dis}(1,n)$，$B_t=\min(\mathrm{dis}(1,a_t)+w_t+\mathrm{dis}(b_t,n),\mathrm{dis}(1,b_t)+w_t+\mathrm{dis}(a_t,n))$​​，​而 $\mathrm{dis}(1,\cdot),\mathrm{dis}(\cdot,n)$ 可以两遍 dij 求出。如果 $t$ 在其上，那么显然 $B_t=\mathrm{dis}(1,n)$，而 $D_t$ 是整张图删掉 $t$ 之后的最短路（事重头戏）。 下面来介绍一下删边最短路的科技（称为科技是因为感觉凭自己想不出来/kk）。首先，$p$ 既是 $1\to n$ 的最短路也事 $n\to 1$ 的最短路，固定住它只考虑删其上的边。显然有结论：$1\to x$​ 的所有最短路中必定存在一条与 $p$ 共享且仅共享一个前缀（可以取最后一个交点，也可用最短路生成树证），$x\to n$、后缀也如此。假设前后缀端点在 $p$ 上的下标为 $pre_x,suf_x$，这显然可以建出最短路树 dfs 一遍求出。但要求 $1$ 为起点、$n$ 为起点的最短路树中 $1\leftrightarrow n$ 路径都是 $p$，这可以在建 $n$ 树时对于最短路上的点强制连边。 以及显然地，删除 $t$ 后的最短路一定是先共享 $p$ 的一段前缀（但不跨过 $t$），然后腾空一段弧绕过 $t$，最后回到 $p$ 上共享 $p$ 的后缀（很好证，$t$ 两边取最迟、早的交点调整）。接下来是最关键的结论：中间这段腾空的弧里，恰好有（显然至少有）一条非最短路树边。也就是说，设弧的两端在 $p$ 上的下标为 $x,y$，恰好存在边 $e$ 使得 $pre_{a_e}=x,suf_{b_e}=y$（当然 $a,b$ 有可能互换）。 考虑反证。假设有至少两条非树边，取任意相邻的两条 $e,f$​​，​如下图：  我们考虑 $1\to b_e$ 的最短路，$pre_{b_e}$ 必然不可能在 $t$ 左侧，那样直接走 $1\to b_e$ 的最短路而非 $1\to a_e\overset{e}{\to} b_e$ 显然会更优；$n\to a_f$ 也事如此，$suf_{a_f}$ 一定在 $t$ 左侧。如下图：  考虑证明这种情况不存在。我们知道 $D$​ 是两端的最短路（因为 $e,f$​ 之间不再有非树边），跟据最短路的拼接定理可知 $\mathrm{dis}(1,a_f)=D+\mathrm{dis}(1,b_e)=\mathrm{dis}(1,suf_{a_f})+C+B+D$​。而另一条路 $\mathrm{dis}(1,suf_{a_f})+A$​ 不是最短路，说明 $C+B+D\leq A$​。同理，考虑 $b_e\to n$​ 最短路可得 $C+A+D\leq B$​。可知 $A-B$​ 和 $B-A$​ 都大于等于 $C+D$​，而 $C+D$​ 事正数，事不可能同时被一个数和它的相反数大于等于的，矛盾！证毕。 这样的话，枚举所有非 $p$​ 中边作为弧上的唯一非树边 $e$​，贡献到 $p$​ 上的下标区间 $[pre_{a_e},suf_{b_e}]$​，贡献值为 $\mathrm{dis}(1,a_e)+w_e+\mathrm{dis}(b_e,n)$​；以及需要交换 $a,b$ 再做一次。这可以线段树，但是事静态的可以直接差分 multiset。于是删边最短路就做完了。 ```cpp #include<bits/stdc++.h> using namespace std; #define int long long #define mp make_pair #define X first #define Y second #define pb push_back const int inf=0x3f3f3f3f3f3f3f3f; const int N=2e5+10; int n,m,qu; int a[N],b[N],w[N]; vector<pair<int,int> > nei[N]; int d1[N],dn[N]; int vis[N]; void dij(int st,int d[]){ for(int i=1;i<=n;i++)d[i]=inf; memset(vis,0,sizeof(vis)); priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; q.push(mp(d[st]=0,st)); while(q.size()){ int x=q.top().Y;q.pop(); if(vis[x])continue;vis[x]=true; for(int i=0;i<nei[x].size();i++){ int y=nei[x][i].X,len=w[nei[x][i].Y]; if(d[x]+len<d[y])d[y]=d[x]+len,q.push(mp(d[y],y)); } } } int fa1[N]; vector<int> son1[N],sonn[N]; int ord[N]; bool cmp(int x,int y){return d1[x]<d1[y];} bool cmp0(int x,int y){return dn[x]<dn[y];} vector<int> ton;int id[N]; int pre[N],suf[N]; void dfs(int x,int las,int p[],vector<int> vec[]){ if(~id[x])las=id[x]; p[x]=las; for(int i=0;i<vec[x].size();i++){ int y=vec[x][i]; dfs(y,las,p,vec); } } int del_dis[N]; vector<int> add[N],del[N]; signed main(){ cin>>n>>m>>qu; for(int i=1;i<=m;i++)scanf("%lld%lld%lld",a+i,b+i,w+i),nei[a[i]].pb(mp(b[i],i)),nei[b[i]].pb(mp(a[i],i)); dij(1,d1),dij(n,dn); for(int i=1;i<=n;i++)ord[i]=i; sort(ord+1,ord+n+1,cmp); for(int _i=2;_i<=n;_i++){ int i=ord[_i]; for(int j=0;j<nei[i].size();j++){ int x=nei[i][j].X,len=w[nei[i][j].Y]; if(d1[x]+len==d1[i]){fa1[i]=x,son1[x].pb(i);break;} } } int x=n; while(true){ // if(n==2e5)cout<<x<<"!!\n"; ton.pb(x); if(x==1)break; x=fa1[x]; } reverse(ton.begin(),ton.end()); memset(id,-1,sizeof(id)); for(int i=0;i<ton.size();i++)id[ton[i]]=i; dfs(1,-1,pre,son1); sort(ord+1,ord+n+1,cmp0); for(int _i=2;_i<=n;_i++){ int i=ord[_i]; if(~id[i])sonn[ton[id[i]+1]].pb(i); else for(int j=0;j<nei[i].size();j++){ int x=nei[i][j].X,len=w[nei[i][j].Y]; if(dn[x]+len==dn[i]){sonn[x].pb(i);break;} } } dfs(n,-1,suf,sonn); memset(vis,-1,sizeof(vis)); for(int i=0;i+1<ton.size();i++){ int x=ton[i],y=ton[i+1]; for(int j=0;j<nei[x].size();j++){ int z=nei[x][j].X,len=w[nei[x][j].Y]; if(z==y&&d1[x]+len==d1[y]){vis[nei[x][j].Y]=i;break;} } } for(int i=1;i<=m;i++)if(!~vis[i]){ int l=pre[a[i]],r=suf[b[i]],v=d1[a[i]]+w[i]+dn[b[i]]; if(l<r)add[l].pb(v),del[r].pb(v); swap(a[i],b[i]); l=pre[a[i]],r=suf[b[i]],v=d1[a[i]]+w[i]+dn[b[i]]; if(l<r)add[l].pb(v),del[r].pb(v); } multiset<int> st; for(int i=0;i+1<ton.size();i++){ for(int j=0;j<add[i].size();j++)st.insert(add[i][j]); for(int j=0;j<del[i].size();j++)st.erase(st.find(del[i][j])); del_dis[i]=st.empty()?inf:*st.begin(); } while(qu--){ int x,v; scanf("%lld%lld",&x,&v); if(!~vis[x])printf("%lld\n",min(d1[n],min(d1[a[x]]+v+dn[b[x]],d1[b[x]]+v+dn[a[x]]))); else printf("%lld\n",min(d1[n]-w[x]+v,del_dis[vis[x]])); } return 0; } ```