在固定起终点的最短路上修改一条边的边权
转换思路很nb。
设修改的边为 \((x,y)\)，边权为 z
不妨设起点为 1，终点为 n。
建出最短路径树，搞出 1-n 的一条链（下文简称“链”）。
记录链经过的边分别为 \(a_i(i\in[1,边数])\)
预处理 1 到所有点的最短距离 \(dis_{1,i}\) 和 n 到所有点的最短距离 \(dis_{n,i}\)
考虑对修改的边进行分类:
-
修改边不在链上
明显答案为 \(min\{dis_{1,n},dis_{1,x}+z+dis_{y,n},dis_{1,y}+z+dis_{x,n}\}\) -
修改边在链上
不妨假设最短路径 1->n 中为 x->y
考虑从图上删除这条边再求最短路。
这等价于求出对于所有 \(u\in[1,x]\)，\(v\in[y,n]\)，先沿链 1->u，再离开链 u->v，最后沿链 v->n 的合法路径的长度最小值。
(此处的 \([1-x]、[y-n]\) 均为链上点)
假设 c 为起点，v 为终点，最短路径为 c->x->y->v
那么 c->x，x->b，b->w，w->y，y->v 就是合法的。这玩意看起来非常难搞，复杂度起飞。想想办法转化一下。
考虑非链边对此的影响。
若我们强制经过一条非链边 \((u,v,w)\)，则贡献为\(min\{dis_{1,u}+w+dis_{v,n},dis_{1,v}+w+dis_{u,n}\}\)
考虑哪些链边能够获得此贡献。
设 1->u 经过的链上的边的最大编号为 a，v->n 经过的链上的边的最小编号为 b
设 a 的相对靠近 n 的端点为 p，b 的相对靠近 1 的端点为 q。
结论：\((u,v,w)\)对编号为\(i\in[a+1,b-1]\)的边有贡献
证明：显然
手摸可以发现并不会在 p->q 的过程中经过链上的边。
反证：设 p->r->s->q,为最优方式,其中r->s为链边。
若 p->r->s->q 更优，则应有最短路1->p->r->s->q->n而非原链，证毕。
那么链上从p到q的边都都可以被更新。
如果有等价路径则尽量离开链。实现中这玩意其实不一定是一段连续前后缀
比如这样：
在有多条最短路径时可以看到不一定要沿着链走。
比如考虑经过\((6,8,2)时\) 1->2->4->5->6->8 可行。
所以才采取最大a，最小b的形式。
code
no such code
#include
using namespace std;
typedef long long ll;
struct edge{
int y,z,nxt;
}e[400010];
int head[200010],cnt;
ll dis[200010];
ll dis1[200010];
ll dis2[200010];
struct data{
int x;
bool operator <(const data &v)const{
return dis[x]>dis[v.x];
}
};
priority_queueq;
int in[400010];
bool inq[200010];
int pr1[200010];
int pr2[200010];
int fr[200010];
ll tree[800010];
ll laz[800010];
int n,m,Q,len;
ll ans;
void add(int x,int y,int z){
cnt++;
e[cnt].y=y;
e[cnt].z=z;
e[cnt].nxt=head[x];
head[x]=cnt;
}
void dij1(){
for(int i=2;i<=n;i++)
dis[i]=2e18;
q.push((data){1});
inq[1]=true;
while(q.size()){
int x=q.top().x;
q.pop(),inq[x]=0;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].y,z=e[i].z;
if(dis[y]>dis[x]+z){
dis[y]=dis[x]+z;
fr[y]=i;
if(inq[y]==0){
q.push((data){y});
inq[y]=true;
}
}
}
}
for(int i=1;i<=n;i++)
dis1[i]=dis[i];
ans=dis[n];
int x=n;
while(x!=1){
//cout<dis[x]+z||(dis[y]==dis[x]+z&&pr2[y]>max(pr2[x],in[i]))){
dis[y]=dis[x]+z;
pr2[y]=max(pr2[x],in[i]);
if(inq[y]==0){
q.push((data){y});
inq[y]=true;
}
}
}
}
for(int i=1;i<=n;i++)
dis2[i]=dis[i];/*,cout<dis[x]+z||(dis[y]==dis[x]+z&&pr1[y]>1;
if(ul<=mid) update(id<<1,l,mid,ul,ur,x);
if(ur>mid) update(id<<1|1,mid+1,r,ul,ur,x);
tree[id]=min(tree[id<<1],tree[id<<1|1]);
}
ll query(int id,int l,int r,int d){
if(l==r) return tree[id];
int mid=(l+r)>>1;
pushdown(id);
if(d<=mid) return query(id<<1,l,mid,d);
else return query(id<<1|1,mid+1,r,d);
}
int main(){
int x,y,z;
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
//cout<