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。于是删边最短路就做完了。

#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;
}