CF1163F Indecisive Taxi Fee
LIdox1536513344
2019-05-12 12:52:34
##### 题意简述
给你一个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)
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
const int MAXM=2e5+5;
const ll Inf=1e18;
struct Original_Edge{
int u,v;ll len;
}oe[MAXM];
struct Node{
int pos;
ll dis;
inline bool operator<(const Node &x)const{
return x.dis<dis;
}
};
struct Edge{
int id,to,nxt;
ll len;
}e[MAXM<<1];
int cnt,head[MAXN];
inline void add_edge(int id,int u,int v,ll len){
e[++cnt].id=id;e[cnt].to=v;e[cnt].nxt=head[u];e[cnt].len=len;head[u]=cnt;
}
int n,m,q;
int ind[MAXN];
int lstvis[MAXN];
int path_cnt,l[MAXN],r[MAXN];
bool On_path[MAXN];
ll disS[MAXN],disT[MAXN];
priority_queue<Node> pq;
ll t[MAXM<<4];
inline void Dijkstra(int s,ll dis[],int f=0){
for(int i=1;i<=n;++i) dis[i]=Inf;
dis[s]=0;
pq.push((Node){s,0});
while(!pq.empty()){
Node fa=pq.top();pq.pop();
int x=fa.pos;
if(fa.dis>dis[x]) continue;
for(int i=head[x],y;i;i=e[i].nxt){
y=e[i].to;
if(dis[y]>fa.dis+e[i].len){
lstvis[y]=e[i].id;
dis[y]=fa.dis+e[i].len;
if(f==1&&!On_path[y]) l[y]=l[x];
if(f==2&&!On_path[y]) r[y]=r[x];
pq.push((Node){y,dis[y]});
}
}
}
}
inline void Trace(){
On_path[1]=true;
l[1]=r[1]=0;
int cur=1;
for(int i=1;cur!=n;++i){
int Edge_id=lstvis[cur];
ind[Edge_id]=i;
++path_cnt;
cur=oe[Edge_id].u^oe[Edge_id].v^cur;
On_path[cur]=true;
l[cur]=r[cur]=i;
}
}
inline void Build(int k,int l,int r){
t[k]=Inf;
if(l==r) return;
int mid=(l+r)>>1;
Build(k<<1,l,mid);
Build(k<<1|1,mid+1,r);
}
inline void Update(int k,int l,int r,int x,int y,ll v){
if(x>y) return;
if(x<=l&&r<=y){
t[k]=min(t[k],v);
return;
}
int mid=(l+r)>>1;
if(x<=mid) Update(k<<1,l,mid,x,y,v);
if(y>mid) Update(k<<1|1,mid+1,r,x,y,v);
}
inline ll Query(int k,int l,int r,int x){
if(l==r) return t[k];
int mid=(l+r)>>1;
ll res=t[k];
if(x<=mid) res=min(res,Query(k<<1,l,mid,x));
else res=min(res,Query(k<<1|1,mid+1,r,x));
return res;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m>>q;
for(int i=1;i<=m;++i){
cin>>oe[i].u>>oe[i].v>>oe[i].len;
add_edge(i,oe[i].u,oe[i].v,oe[i].len);
add_edge(i,oe[i].v,oe[i].u,oe[i].len);
ind[i]=-1;
}
Dijkstra(n,disT);
Trace();
Dijkstra(1,disS,1);
Dijkstra(n,disT,2);
Build(1,1,path_cnt);
for(int i=1;i<=m;++i){
if(ind[i]==-1){
Update(1,1,path_cnt,l[oe[i].u]+1,r[oe[i].v],disS[oe[i].u]+oe[i].len+disT[oe[i].v]);
Update(1,1,path_cnt,l[oe[i].v]+1,r[oe[i].u],disS[oe[i].v]+oe[i].len+disT[oe[i].u]);
}
}
for(int i=1;i<=q;++i){
int Edge_id;ll New_len,ans=disS[n];
cin>>Edge_id>>New_len;
if(ind[Edge_id]!=-1){
ans=disS[n]-oe[Edge_id].len+New_len;
if(New_len>oe[Edge_id].len)
ans=min(ans,Query(1,1,path_cnt,ind[Edge_id]));
}
else{
if(New_len<oe[Edge_id].len){
ans=min(ans,disS[oe[Edge_id].u]+New_len+disT[oe[Edge_id].v]);
ans=min(ans,disS[oe[Edge_id].v]+New_len+disT[oe[Edge_id].u]);
}
}
cout<<ans<<endl;
}
return 0;
}
```