另一种做法，更优更好写：

这里不需要线段树，查询没有 $log$，只需要一点点的转化，便可以用暴力解决问题。

思路：

相比其他题解，思路大框架并未改变，在此简要说明，并解释我当时没理解的点：

• 找出最短路，记为 $E$，并将其经过的边从起点到终点重编号

• 将询问按照：是否在 $E$ 上，边权增大还是变小分为 $4$ 类

• 经讨论，只需要特殊处理在最短路上，边权变大的信息

• 记录：

  • $L[u]$ 表示 $u$ 在自己所属的最短路中，上次一经过 $E$ 中边的编号
  • $R[u]$ 表示 $u$ 在自己所属的最短路中，下一次经过 $E$ 中边的编号的上一个
  • 由此，$u$ 所在的最短路经过原图上的边是 $[1,L[u]],[R[u]+1,cnt]$

• 对于每个 $1$ 类询问，只需处理不经过他这条边的最短路

• 对于每条非 $E$ 边，我们可以利用 $L,R$ 的信息，来更新。具体而言，对于一条有向边 $(u,v)$，设经过他的最短路长度为 $S$，则不经过原图中 $[L[u]+1,R[u]]$ 这一段路径的任意一条鞭的最短路都不会比 $S$ 大。本质是一个区间 $min$ 覆盖问题。

• 最终答案单点查询。

整个过程中，复杂度瓶颈在于最后的 $min$ 覆盖问题。

设每一次覆盖形如 $(l,r,v)$ 表示将 $[l,r]$ 这一段的最小值和 $v$ 更新。

考虑暴力过程：直接从 $l$ 枚举到 $r$，然后不断取 $min$

优化这个暴力：一个性质是很显然但不易发现的：一个位置被一个已知更小的数更新后，不会再被一个已知更大的数更新。

举个例子，某个位置依次被 $2,3,5,6$ 覆盖，那么当它被 $2$ 覆盖后，之后的覆盖都为无效覆盖。而暴力浪费的时间都在无效覆盖上。

考虑如何只进行有效覆盖：我们将每条覆盖离线并按照覆盖值从小到大排序，这样就可以保证每一段里面，没有被之前覆盖的位置都应该更新为当前数。

由于一个位置只会被覆盖一次，我们可以用一个类似区间开根号的想法，用并查集维护每个位置应该被更新的位置是谁。

对于预处理来说，需要排序，因此和线段树没有差异。

对于查询来说，这里是 $O(1)$ 的，而线段树是 $O(log_2n)$

相比什么 $multiset$ 维护 $min$ 差分，我觉得总之都是离线，这样不更好写常数更小吗？

相比线段树要么需要维护懒标记，要么需要标记可持久化，并查集优化暴力写法更直观更好写。（我不会告诉你我调了2h这道题挂拍后发现自己线段树写挂了）

贴上我丑陋的代码：

#include<bits/stdc++.h>
#define int long long
#define ls u*2
#define rs u*2+1
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10,M=N*2,inf=1e18;
int S,T;
struct Edge
{
	int u,v,w;
}edge[N];
int id[M];//下标为i的边在重编号中的数字 
int h[N],e[M],ne[M],w[M],idx;
int nidx[M];//在idx为下标下的题目编号
int dist[2][N];
bool st[N],is[N];
int pre[N],L[N],R[N];
int n,m,q,ecnt;
namespace Dsu
{
	struct Query
	{
		int l,r,v;
		bool operator<(const Query &t)const
		{
			return v<t.v;
		}
	}query[M*2];
	int tot;
	int p[N],ans[N];
	void init()
	{
		for(int i=1;i<=ecnt+1;i++) p[i]=i,ans[i]=inf;//注意，必须多处理出来一位
	}
	int find(int x)
	{
		if(x!=p[x]) p[x]=find(p[x]);
		return p[x];
	}
	void mark(int l,int r,int c)
	{
		for(int i=find(l);i<=r;i=find(i))
		{
			ans[i]=c;
			p[i]=i+1;
		}
	}
	void mark()
	{
		sort(query+1,query+1+tot);
		for(int i=1;i<=tot;i++)
		{
			int l=query[i].l,r=query[i].r,v=query[i].v;
			mark(l,r,v);
		} 
	}
}

void add(int i,int a,int b,int c)
{
	nidx[idx]=i,e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dijkstra(int x,int dist[],int t)
{
	priority_queue<PII,vector<PII>,greater<PII>> heap;
	for(int i=1;i<=n;i++) dist[i]=inf,st[i]=false;
	dist[x]=0,heap.push({dist[x],x});
	while(heap.size())
	{
		auto it=heap.top();heap.pop();
		int u=it.second;
		if(st[u]) continue;
		st[u]=true;
		for(int i=h[u];~i;i=ne[i])
		{
			int v=e[i];
			if(dist[v]>dist[u]+w[i])
			{
				dist[v]=dist[u]+w[i],pre[v]=i;
				if(t==1&&!is[v]) L[v]=L[u];
				if(t==2&&!is[v]) R[v]=R[u];
				heap.push({dist[v],v});
			}
		}
	}
}

void get_path()
{
	int u=S;
	is[u]=true,L[u]=R[u]=0;
	for(int j=1;u!=T;j++) 
	{
		int i=pre[u];
		id[nidx[i]]=++ecnt;
		u=e[i^1];
		is[u]=true;
		L[u]=R[u]=ecnt;
	}
}

signed main()
{
	using namespace Dsu;

    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	memset(h,-1,sizeof h);
	cin>>n>>m>>q;
	for(int i=1,a,b,c;i<=m;i++)
	{
		cin>>a>>b>>c;
		add(i,a,b,c),add(i,b,a,c);
		edge[i]={a,b,c};
	}

	S=1,T=n;
	dijkstra(T,dist[1],0);
	
	get_path();

	dijkstra(S,dist[0],1);
	dijkstra(T,dist[1],2);
	
	for(int i=1,len;i<=m;i++)
	{
		if(id[i]) continue;
		int u=edge[i].u,v=edge[i].v,w=edge[i].w;
		len=dist[0][u]+w+dist[1][v];
		if(len<inf&&L[u]+1<=R[v]) query[++tot]={L[u]+1,R[v],len};
		len=dist[0][v]+w+dist[1][u];
		if(len<inf&&L[v]+1<=R[u]) query[++tot]={L[v]+1,R[u],len};
	}
	
    init();
	mark();

	int mind=dist[0][T];
	while(q--)
	{
		int i,x;
		cin>>i>>x;
		int u=edge[i].u,v=edge[i].v,w=edge[i].w;
        
        int minv;
		if(!id[i]) minv=min(mind,min(dist[0][u]+x+dist[1][v],dist[0][v]+x+dist[1][u]));
		else minv=min(mind-w+x,ans[id[i]]);
        cout<<minv<<"\n";
	}
	
	return 0;
}

给你一个n个点，m条边的无向图，每条边连接点u、v，并且有个长度w。 有q次询问，每次询问给你一对t、x,表示仅当前询问下，将t这条边的长度修改为x,请你输出当前1到n的最短路长度。

数据范围

2 ≤ n ≤ 2e5 1 ≤ m, q ≤ 2e5 1 ≤ wi,xi ≤ 1e9

我们先不考虑修改，考虑给出指定的边，求出经过这条边的最短路 设这条边连接u,v,很容易想到这样的话只需要从1与n分别跑一遍Dijkstra,最短路长度就是 min(1到u的距离+边长+v到n的距离,1到v的距离+边长+u到n的距离)。

我们可以把修改分为以下几类： *1.修改的边在1到n的最短路上，边的长度变大了。 *2.修改的边在1到n的最短路上，边的长度变小了。 *3.修改的边不在1到n的最短路上，边的长度变大了。 *4.修改的边不在1到n的最短路上，边的长度变小了。

很容易知道： 对于2， 原最短路长度-原边长+新边长 就是答案。 对于3， 原最短路长度 就是答案。 对于*4， 由前面的思考得 min(原最短路长度，min(1到u的距离+新边长+v到n的距离,1到v的距离+新边长+u到n的距离) 就是答案。

都是O(1)得出答案

于是只剩下*1了。 对于原问题，我们可以得到一些简单的结论。 令原最短路为E,其路径为E1,E2,E3……Ek. 对于每个不是E上的点u,1到u的最短路必定会使用E的一段前缀（可以为空）。 令这个前缀为Lu,1到u的最短路经过E1,E2,……E(Lu)。

同理可得u到n的最短路必定会使用E的一段后缀（可以为空）。 令这个后缀为Ru,u到n的最短路经过E1,E2,……E(Ru)。

特别地，对于E上的点u，令其L为E上连接自己的边的编号，R为自己连到下一个E上点的边的编号的上一个

关于如何求出每个点的L与R,我们可以先从n到1跑一遍Dijkstra,求出E的路径。 然后分别从1到n,n到1各跑一遍Dijkstra,过程中分别更新每个非E上点的L,R。

有了每个点的L,R后，考虑如何解决*1。 *1就是求min(E的长度-原边长+新边长，不经过修改的这条边的最短路长度)

问题从而转化成如何快速求出 不经过E上某条边的最短路长度

考虑使用线段树，树上的每段区间 l,r 的值表示 整个图不经过E上l到r这段的最短路长度

有了每个点的L,R我们很容易用图中非E上的边更新线段树

例如：一条边连接点u,v,经过这条边的最短路长度为len， 我们可以把树上 Lu+1,Rv 的区间用len更新,比个min, 同样地，可以把 Lv+1,Ru 的区间用len更新 **由于代码中点1的l,r为0，且l=r,所以l要加1 **如果图方便，可以把l[1]=1,r[1]=0,每个点的l比r大1 **不懂的话可以自己画图比划比划

从而我们可以在O(logn)的时间内回答每个问题 总的复杂度为O((m+n+q)logn)

#include<bits/stdc++.h>
#define int long long
#define ls u*2
#define rs u*2+1
using namespace std;
typedef pair<int,int> PII;
const int N=4e5+10,M=N*2,inf=1e18;
int S,T;
namespace SGT
{
	struct Tree
	{
		int l,r;
		int minv;
	}tr[N*4];
	void build(int u,int l,int r)
	{
		tr[u]={l,r,inf};
		if(l==r) return;
		int mid=l+r>>1;
		build(ls,l,mid),build(rs,mid+1,r);
	}
	void modify(int u,int l,int r,int c)
	{
		if(l>r) return;
		if(tr[u].l>=l&&tr[u].r<=r) tr[u].minv=min(tr[u].minv,c);
		else
		{
			int mid=tr[u].l+tr[u].r>>1;
			if(l<=mid) modify(ls,l,r,c);
			if(r>mid) modify(rs,l,r,c);
		}
	}
	int query(int u,int x,int res)
	{
		if(tr[u].l==tr[u].r) return min(tr[u].minv,res);
		res=min(res,tr[u].minv);
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid) return query(ls,x,res);
		else return query(rs,x,res);
	}
}

struct Edge
{
	int u,v,w;
}edge[M];
int id[M];//下标为i的边在重编号中的数字 
int h[N],e[M],ne[M],w[M],idx;
int nidx[M];//在idx为下标下的题目编号
int dist[2][N];
bool st[N],is[N];
int pre[N],L[N],R[N];
int n,m,q,ecnt;

void add(int i,int a,int b,int c)
{
	nidx[idx]=i,e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dijkstra(int x,int dist[],int t)
{
	priority_queue<PII,vector<PII>,greater<PII>> heap;
	for(int i=1;i<=n;i++) dist[i]=inf,st[i]=false;
	dist[x]=0,heap.push({dist[x],x});
	while(heap.size())
	{
		auto it=heap.top();heap.pop();
		int u=it.second;
		if(st[u]) continue;
		st[u]=true;
		for(int i=h[u];~i;i=ne[i])
		{
			int v=e[i];
			if(dist[v]>dist[u]+w[i])
			{
				dist[v]=dist[u]+w[i],pre[v]=i;
				if(t==1&&!is[v]) L[v]=L[u];
				if(t==2&&!is[v]) R[v]=R[u];
				heap.push({dist[v],v});
			}
		}
	}
}

void get_path()
{
	int u=S;
	is[u]=true,L[u]=R[u]=0;
	for(int j=1;u!=T;j++) 
	{
		int i=pre[u];
		id[nidx[i]]=++ecnt;
		u=e[i^1];
		is[u]=true;
		L[u]=R[u]=ecnt;
	}
}

signed main()
{
	using namespace SGT;

    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	memset(h,-1,sizeof h);
	cin>>n>>m>>q;
	for(int i=1,a,b,c;i<=m;i++)
	{
		cin>>a>>b>>c;
		add(i,a,b,c),add(i,b,a,c);
		edge[i]={a,b,c};
	}

	S=1,T=n;
	dijkstra(T,dist[1],0);
	
	get_path();

	dijkstra(S,dist[0],1);
	dijkstra(T,dist[1],2);
	
	build(1,1,ecnt);
	
	for(int i=1;i<=m;i++)
	{
		if(id[i]) continue;
		int u=edge[i].u,v=edge[i].v,w=edge[i].w;
		int len=dist[0][u]+w+dist[1][v];
		modify(1,L[u]+1,R[v],len);
		len=dist[0][v]+w+dist[1][u];
		modify(1,L[v]+1,R[u],len);
	}

	int mind=dist[0][T];
	while(q--)
	{
		int i,x,ans=mind;
		cin>>i>>x;
		int u=edge[i].u,v=edge[i].v,w=edge[i].w;
        
		if(!id[i])
		{
			int minv=min(dist[0][u]+x+dist[1][v],dist[0][v]+x+dist[1][u]);
			cout<<min(minv,mind)<<"\n";
		}
		else
		{
			int p=id[i];
			int minv=min(mind-w+x,query(1,p,inf));
			cout<<minv<<"\n"; 
		}
	}
	
	return 0;
}