D. Navigation System(逆序最短路)

Problem - 1321D - Codeforces

题意:给你n个点,m条单向边的图,边权均为1,再给你k个点,要求从a1走到ak,如果途中从一个点走到下一个点的最短路径所规划的线路,与题中给的线路不同,就会发生路线重建,问路线重建的最小次数与最大次数是多少.

题解:

首先我们应该想到无论现在在哪个点,我们最终的目的都是要走到ak,所以不妨以ak为起点,找到到其他任何点的最短路

(注意建图时要反向建图,因为图是单向图,我们是从终点开始找)

其次,遍历i~k的点,遍历之前要把正向边再加上,否则无法正向遍历

如果建图方式与我代码一样

(注意要再次初始化头节点,因为之前建图时的是反向建图,头节点并不是真正的头节点)

做完上述准备工作,我们就可以正式开始遍历了

l = ai , r = ai+1

如果d[l] <= d[r],说明 l 此时离终点更近或者和下一个要走的点离终点一样近,因为按最短路是不会走r这个点的,但是走了,所以一定会发生重建,mi++,ma++;

其他情况是除了r还有点满足即使走了,也是最短路的情况,所以遍历此时的l点往后,看是否有这种情况,如果有ma++,(break此时遍历l点),(因为只用判断此时有没有就行,不用考虑有几个点满足)

#include
#include
#include
using namespace std;
int n,m,k;
typedef pair<int,int> PII; 
const int N = 4e5+10;
int e[N],h[N],ne[N],idx; 
int d[N];
int a[N];
int vis[N];
int x[N],y[N];
void add(int l,int r)
{
	e[idx] = r;
	ne[idx] = h[l];
	h[l] = idx++;
}
void djk()
{
	priority_queue,greater> q;
	d[a[k]] = 0;
	q.push({0,a[k]});
	while(q.size())
	{
		PII tem = q.top();
		q.pop();
		int ver =tem.second,dis = tem.first;
		if(vis[ver])
		continue;
		vis[ver] = 1;
		for(int i = h[ver];i != -1;i = ne[i])
		{
			int j = e[i];
			if(d[j] > dis + 1)
			{
				d[j] = dis +1;
				q.push({d[j],j});
			}
		}
	}
 }
 
 
 
 
 
 
int main()
{
	memset(h,-1,sizeof h);
	memset(d,0x3f,sizeof d);
	cin >> n >>m;
	for(int i = 1; i <= m;i++)
	{
		cin >> x[i] >> y[i];
		add(y[i],x[i]);
	} 
	cin >> k;
	for(int i = 1;i <= k;i ++)
	cin >> a[i];
	djk();
	int mi = 0,ma = 0;
	memset(h,-1,sizeof h);
	for(int i = 1;i <= m;i++)
	{
		add(x[i],y[i]);
	}
	for(int i = 1;i < k;i++)
	{
		int l = a[i],r = a[i+1];
		if(d[l] <= d[r] )
		{
			ma ++ ,mi ++; 
		}
		else
		{
			for(int j = h[l];j != -1;j = ne[j])
			{
				int p = e[j];
				if(d[p] == d[l] - 1&&p != r)
				{
					ma++;
					break;
				}
			}
		}
	}
	cout << mi <<" "<
	
}