洛谷 [HNOI2014]道路堵塞 解题报告

时间：2022-02-08 10:15:30

[HNOI2014]道路堵塞

题意

给一个有向图并给出一个这个图的一个\(1\sim n\)最短路，求删去这条最短路上任何一条边后的最短路。

又事SPFA玄学...

有个结论，新的最短路一定是\(1\sim l,l\sim r,r\sim n\)组成的，中间一段是非最短路，两边是原最短路

先删去最短路

然后从1开始枚举短边，按顺序维护\(1\sim i\)前\(i\)个点连到\(r\sim n\)的最小值，发现我们要根据\(r\)的变换进行删除，可以拿一个堆维护。

剩下的对每个点跑跑\(SPFA\)就可以了，每次注意删去不参与松弛的那条边。

感性上是只跑了一次\(SPFA\)的

Code:

#include <cstdio>

#include <cstring>

#include <queue>

#include <cctype>

int read()

{

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int N=2e5+10;

int head[N],to[N],Next[N],edge[N],cnt;

void add(int u,int v,int w)

{

    to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;

}

struct node{int u,v,w;}E[N];

int n,m,L,used[N],dis[N],disl[N],disr[N],num[N],ban[N],path[N],s[N],vis[N],tot;

struct yuucute

{

	int v,w;

	bool friend operator <(yuucute a,yuucute b){return a.w>b.w;}

}yuu[N];

std::priority_queue <yuucute> Q;

void spfa(int ss,int ban,int tim)

{

	dis[ss]=disl[ss];

	std::queue <int> q;

	q.push(ss);

	tot=0;

	while(!q.empty())

	{

		int now=q.front();

		q.pop();

		used[now]=0;

		for(int v,i=head[now];i;i=Next[i])

			if(((v=to[i])!=ban||now!=ss)&&dis[v]>dis[now]+edge[i])

			{

				dis[v]=dis[now]+edge[i];

				if(num[v]>tim){if(vis[v]!=tim) vis[s[++tot]=v]=tim;}

				else if(!used[v]) {q.push(v);used[v]=1;}

			}

	}

	while(tot)

	{

		int now=s[tot--];

		if(!yuu[now].v||yuu[now].w>dis[now]+disr[now])

		{

			yuu[now].w=dis[now]+disr[now];

			yuu[now].v=now;

			Q.push(yuu[now]);

		}

	}

}

int main()

{

	n=read(),m=read(),L=read();

	for(int i=1;i<=m;i++) E[i].u=read(),E[i].v=read(),E[i].w=read();

	for(int i=1;i<=L;i++)

	{

		ban[path[i]=read()]=1;

		num[E[path[i]].u]=i;

		disl[E[path[i]].v]=disl[E[path[i]].u]+E[path[i]].w;

	}

	num[n]=L+1;

	for(int i=L;i;i--) disr[E[path[i]].u]=disr[E[path[i]].v]+E[path[i]].w;

	for(int i=1;i<=m;i++) if(!ban[i]) add(E[i].u,E[i].v,E[i].w);

	memset(dis,0x3f,sizeof dis);

	for(int i=1;i<=L;i++)

	{

		spfa(E[path[i]].u,E[path[i]].v,i);

		while(!Q.empty()&&num[Q.top().v]<=i) Q.pop();

		if(Q.empty()) puts("-1");

		else printf("%d\n",Q.top().w);

	}

	return 0;

}

2019.2.18

相关文章