题解：P11795 [JOI 2016 Final] 铁路票价 / Train Fare

一个基于离线特性而比较容易理解的题解

有一个特性：

把一条边边权增大，之后包含它的路径一定比原最短路权值大。

也就意味着加权值的操作效益等同于删边。

再看到输入的离线特性，就容易想到将边加一个第二权值，定义为 此边何时被删去。

定义一条

1

到

i

点的最短路被破坏，即为无论如何

1

到

i

点的路径无法小于等于原最短路的长度。

因为所有边长度为

1

，故我们可以使用 BFS 来求单源最短路，顺便求

1

到

i

点的最短路被破坏的时间。

需要注意的是，此处 BFS 来求单源最短路时要考虑到最短路路径相等时也要更新答案。

最后把时间计数排序一下，再用前缀和算一下此时已有多少路径被破坏，然后按

q

输出。

本题，完。

CPP

#include <bits/stdc++.h>
using namespace std;
struct edge
{
	int u,v,lo;
	bool operator <(const edge &a)const
	{
		return lo>a.lo;
	}
}ed[1000005];
vector <edge>a[100005];
int n,m,q,dis[1000005],dis2[1000005],tpx[1000005],sum[1000005];
void bfs()
{
	for(int i=1;i<=1000000;i++) dis[i]=99999999;
	dis2[1]=99999999;
	dis[1]=0;
	queue<int> q;
	q.push(1);
	long long flag=1;
	while(q.size())
	{
		int now=q.front();
		q.pop();
		for(int i=0;i<a[now].size();i++)
		{
			if(flag)
			{
				if(dis[a[now][i].v]>dis[now]+1)
				{
					q.push(a[now][i].v);
					dis[a[now][i].v]=dis[now]+1;
					dis2[a[now][i].v]=min(dis2[now],a[now][i].lo);
				}
				if(dis[a[now][i].v]==dis[now]+1)
				{
					dis2[a[now][i].v]=max(dis2[a[now][i].v],min(dis2[now],a[now][i].lo));
				}

			}
		}
	}
}
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		cin>>ed[i].u>>ed[i].v;
		ed[i].lo=99999999;
	}
	for(int i=1;i<=q;i++)
	{
		int x;
		cin>>x;
		ed[x].lo=i;
	}
	for(int i=1;i<=m;i++)
	{
		a[ed[i].u].push_back(ed[i]);
		a[ed[i].v].push_back({ed[i].v,ed[i].u,ed[i].lo});
	}
	bfs();
	for(int i=1;i<=n;i++)
	{
		if(dis2[i]<1000000)tpx[dis2[i]]++;
	}
	for(int i=1;i<=q;i++)
	{
		sum[i]=sum[i-1]+tpx[i];
		cout<<sum[i]<<endl;
	}
	return 0;
}

题解：P11795 [JOI 2016 Final] 铁路票价 / Train Fare

文章操作

一个基于离线特性而比较容易理解的题解

相关推荐

评论

题解：P11795 [JOI 2016 Final] 铁路票价 / Train Fare