CF346D Robot Control

题目描述

CF346D Robot Control

思路

可以想到，对于每一个节点，$dp[x]$ 表示其走到终点所需的最少指令数。考虑状态的转移：如果下指令，则 $dp[i]$ 为其出边所通向的点中的最小值加一。若不下指令则取最大值，两种情况取最小值。即，
$$
dp[x]=\min\{\min_{x\to y}\{dp[y]\}+1,\max_{x\to y}\{dp[y]\}\}
$$
你能解决问题的一部分吗？

可以发现下指令的部分类似于一个边权为 $1$ 的最短路，尝试用 $BFS$ 解决。我们先对 $BFS$ 的过程进行一下概括，$BFS$ 时队列中的元素如下：

可以发现，队列中元素（指 $dp$ 值）总是连续的 $n$ 和 $n+1$，且不降。在反图上 $BFS$，每次取队首元素进行更新，从队尾插入。

再考虑不钦定前进方向的情况。（称“第二类”）

枚举 $x$ 的所有出边（在原图上），如果发现指向的点的 $dp$ 值的最大值小于 $dp[x]$，则更新，同时在队首插入 $x$ 以保证单调性在 $x$ 出队时，如果 $x$ 能被第二类更新，显然它应该先被更新再更新别的点，这样不会在非最优值上浪费时间，而此时第二类更新 $x$ 的点一定已经被更新，因此 $x$ 一出队就对其更新，时间复杂度正确，而正确性显然。

Code

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;

int dp[1000001],n,m,t[1000001],tt[1000001],S,T;
bool vis[1000001];
int cnt1,cnt2;
class graph
{public:
	int to,nxt;
}edge[2000010],egde[2000010];

int l,r;
int que[2000010];

#define emp (l>r)
#define L que[l]
#define pop vis[que[l++]]=0
#define pl(x) vis[x]=1,que[--l]=x
#define pr(x) vis[x]=1,que[++r]=x
#define to1 edge[i].to
#define to2 egde[i].to

inline void add(int v,int u)
{
	edge[++cnt1].to=u;
	edge[cnt1].nxt=t[v];
	t[v]=cnt1;
}

inline void Add(int v,int u)
{
	egde[++cnt2].to=u;
	egde[cnt2].nxt=tt[v];
	tt[v]=cnt2;
//	++deg[v];
}//反图

int main()
{
 	#ifdef usm
	freopen("input.in","r",stdin);
	freopen("output.out","w",stdout);
	#endif
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		Add(v,u);
	}
	scanf("%d%d",&S,&T);
	
	memset(dp,0x3f,sizeof(dp));
	l=1000001,r=1000000;
	dp[T]=0;
	que[++r]=T;
	while(!emp)//BFS
	{
		int _=L;
		pop;
		int mx=0;
		for(int i=t[_];i;i=edge[i].nxt)if(dp[to1]>mx)
				mx=dp[to1];
		if(dp[_]>mx)
		{
			dp[_]=mx;
			if(!vis[_])pl(_);
			continue;
		}
		for(int i=tt[_];i;i=egde[i].nxt)
		if(dp[_]+1<dp[to2])
		{
			dp[to2]=dp[_]+1;
			if(!vis[to2])
				pr(to2);
		}
	}
	if(dp[S]!=inf)printf("%d",dp[S]);
	else puts("-1");
	return 0;
}