这道题我们老师上课讲了，回来琢磨了琢磨，还是不太会，又借鉴了一下博客

话说这道题真坑，首先显然是可以dp的，方程为dp[u]=min(min(dp[v]+1),max(dp[v]))dp[u]=min(min(dp[v]+1),max(dp[v]))

这里dp[i]表示第i个点到终点需要的指令数量，

其实这个方程是可以直接 BFS 来算的...

注意到 min(dp(v) + 1) 实际上就是一个边权为 1 的最短路, 也就是 BFS;

而考虑后一项 maxfdp(v)g, 其实是在 BFS 时最后一个更新它的节点去更新它时没有代价.
因为 BFS 的正确性要求队列中的元素距离是不降的, 所以一旦
某个节点被最后一个点更新, 那么我们需要把它加入队首而非队尾.
这个做法是 O(N + M) 的, 因为每个节点我们只需用它更新一次. 一样的道理, 每个点只会入队至多两次

这里我们借助spfa来完成dp

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dp[2000000], head[1100000], head2[1100000], len, len2;
struct edge{
	int v, fail;
	edge(){}
	edge(int a, int c){
		v = a;
		fail = c;
	}
}e[2200000],e2[2200000];
void add(int a, int b){
	e[len] = edge(b, head[a]);
	head[a] = len++;
}
void Add(int a, int b){
	e2[len2] = edge(a, head2[b]);
	head2[b] = len2++;
}
int vis[2200000];
queue<int> q;
int main(){
	ios::sync_with_stdio(0);
	memset(head, -1, sizeof(head));
	memset(head2, -1, sizeof(head2));
	int n, m, s, t;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y, z;
		cin >> x >> y;
		add(x, y);
		Add(x, y);//建正图，反图，方便dp
	} 
	cin >> s >> t;
	for(int i = 1; i <= n + 20; i++){//初始化
		dp[i] = 1147483646;
	}
	vis[t] = 1;
	dp[t] = 0;
	q.push(t);
	while(!q.empty()){//spfa模板稍加改动
		int now = q.front();
		q.pop();
		vis[now] = 0;
      //这里的两个for就分别对应前面转移方程的两种情况
		for(int i = head2[now]; ~i; i = e2[i].fail){
			if(dp[e2[i].v] > dp[now] + 1){
				dp[e2[i].v] = dp[now] + 1;
				if(!vis[e2[i].v]){
					vis[e2[i].v] = 1;
					q.push(e2[i].v);
				}
			} 
		}
		int Max = 0;
		for(int i = head[now]; ~i; i = e[i].fail){
			Max = max(Max, dp[e[i].v]);
		}
		if(dp[now] > Max){
			dp[now] = Max;
			if(!vis[now]){
				vis[now] = 1;
				q.push(now);
			}
		}
	}
	if(dp[s] != 1147483646)
	cout << dp[s] << endl;
	else cout << -1 << endl;
	return 0;
}