codeforces1163 F Indecisive Taxi Fee

题面

题意

给出一张无向图,每次询问修改一条边的权值,并询问此时点1到点n的最短路的长度,询问之间相互独立.

做法

首先将修改分成以下三种情况:

1.修改了非最短路上的边,则最短路变为 min ⁡ ( \min( min(原来的最短路长度 , d [ 1 ] [ u ] + d [ v ] [ n ] + l e n ) ,d[1][u]+d[v][n]+len) ,d[1][u]+d[v][n]+len)

2.修改了最短路上的边,且比原来短,则最短路变为原来的最短路长度减去修改减小的权值.

3.修改了最短路上的边,且比原来长,这种情况最难处理.

这种情况又可以分为两小类:

1.最短路为原来最短路长度+因修改而增大的长度

2.最短路为一条不经过修改边的路径

下面考虑第二小类:

首先可以以点1,n分别为源点建出最短路树,则一条可能的最短路最多只经过一条非树边,因此我们可以考虑每条非树边在修改哪些树边后有可能出现在最短路中.而这些树边正好构成一条链,因此这就相当于对一条链进行区间取最小值,然后就可以求出删掉每条最短路上的边后的最短路径是多少了,与之前几类结合后即可求解.

代码

#include<bits/stdc++.h>
#define ll long long
#define P pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define INF 0x3f3f3f3f3f3f3f3f
#define N 200100
using namespace std;

ll n,m,Q,bb=1,A[N],B[N],C[N],fa[N],first[N],nxt[N],id[N],ans[N],d[2][N];
bool in[N],sb[N];
struct Bn
{
	ll to,next,quan;
}bn[N<<1];
multiset<ll>se;
vector<ll>to[N],ad[N],del[N];
priority_queue<P,vector<P>,greater<P> >pq;

inline void add(ll u,ll v,ll w)
{
	bb++;
	bn[bb].to=v;
	bn[bb].next=first[u];
	bn[bb].quan=w;
	first[u]=bb;
}

inline void Dij(ll s,ll *d)
{
	ll i,t,p,q;
	d[s]=0;
	pq.push(mp(0,s));
	for(;!pq.empty();)
	{
		P now=pq.top();
		pq.pop();
		if(now.fi>d[now.se]) continue;
		for(p=first[now.se];p!=-1;p=bn[p].next)
		{
			ll t=now.fi+bn[p].quan;
			if(t>=d[bn[p].to]) continue;
			d[bn[p].to]=t;
			fa[bn[p].to]=now.se;
			pq.push(mp(t,bn[p].to));
		}
	}
}

void dfs(ll now)
{
	ll i,t;
	for(i=0;i<to[now].size();i++)
	{
		t=to[now][i];
		if(!id[t]) id[t]=id[now];
		dfs(t);
	}
}

int main()
{
	memset(first,-1,sizeof(first));
	memset(d,0x3f,sizeof(d));
	ll i,j,t,p,q,o;
	cin>>n>>m>>Q;
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&p,&q,&o);
		add(p,q,o),add(q,p,o);
		A[i]=p,B[i]=q,C[i]=o;
	}
	Dij(n,d[1]),Dij(1,d[0]);
	fa[1]=0;
	for(i=2;i<=n;i++)
	{
		if(d[0][i]==INF) continue;
		to[fa[i]].push_back(i);
		for(p=first[fa[i]];bn[p].to!=i || bn[p].quan+d[0][fa[i]]!=d[0][i];p=bn[p].next);
		sb[p>>1]=1;
	}
	for(i=n;i!=1;i=fa[i])
	{
		nxt[fa[i]]=i;
		for(p=first[i];bn[p].to!=fa[i] || bn[p].quan+d[1][i]!=d[1][fa[i]];p=bn[p].next);
		in[p>>1]=1;
	}
	for(i=j=1;i;i=nxt[i],j++) id[i]=j;
	dfs(1);
	for(i=1;i<=m;i++)
	{
		p=A[i],q=B[i];
		if(sb[i]) continue;
		if(id[p]>id[q]) swap(p,q);
		ad[id[p]].push_back(d[0][p]+d[1][q]+C[i]);
		del[id[q]].push_back(d[0][p]+d[1][q]+C[i]);
	}
	se.insert(INF);
	for(i=1;i<id[n];i++)
	{
		for(j=0;j<ad[i].size();j++) se.insert(ad[i][j]);
		for(j=0;j<del[i].size();j++) se.erase(se.find(del[i][j]));
		ans[i]=*se.begin();
	}
	while(Q--)
	{
		scanf("%lld%lld",&t,&o);
		p=A[t],q=B[t];
		if(in[t]) printf("%lld\n",min(ans[min(id[p],id[q])],d[0][n]-C[t]+o));
		else printf("%lld\n",min(d[0][n],min(d[0][p]+d[1][q],d[0][q]+d[1][p])+o));
	}
}