[CodeForces238E]Meeting Her（图论+记忆化搜索）

Description

题目链接:Codeforces

Solution

因为路线随机，所以找出各路线最短路必须经过的点，在这个点必定能上车

直接floyd暴力找割点

然后不断用k条公交车路线来更新DP答案，直到更新不了为止，dp[i]表示从点i到终点的答案

Code

#include <cstdio>
#include <algorithm>
#include <cstring> 
#define N 1100 
using namespace std;

int n,m,g[N][N],S,T,s[N],t[N],dp[N],cnt[N],Ans[N];
bool cut[N][N],vis[N]; 

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int dfs(int u,int cur){
	if(vis[u]) return dp[u];
	vis[u]=1;int tmp=-1;
	for(int v=1;v<=n;++v)
		if(g[u][v]==1&&g[u][t[cur]]==g[v][t[cur]]+1)
			tmp=max(tmp,dfs(v,cur));
	if(tmp==-1) tmp=1e9;
	tmp=min(tmp,Ans[u]);
	return dp[u]=tmp;
}

int main(){
	n=read(),m=read(),S=read(),T=read();
	memset(g,0x3f,sizeof(g));
	for(int i=1;i<=n;++i)g[i][i]=0;//注意自己到自己初始化为0
	while(m--){
		int u=read(),v=read();
		g[u][v]=1;//有向图
	}
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
	m=read();
	for(int k=1;k<=m;++k){
		s[k]=read(),t[k]=read();
		if(g[s[k]][t[k]]==0x3f3f3f3f)continue;//这里不特判会RE
		for(int i=1;i<=n;++i)
			if(g[s[k]][i]+g[i][t[k]]==g[s[k]][t[k]])
				cnt[g[s[k]][i]]++;
		for(int i=1;i<=n;++i)
			if(g[s[k]][i]+g[i][t[k]]==g[s[k]][t[k]]){
				if(cnt[g[s[k]][i]]==1) cut[k][i]=1;
				cnt[g[s[k]][i]]=0;
			}
	}
	
	bool flag=1;
	memset(dp,0x3f,sizeof(dp));
	memset(Ans,0x3f,sizeof(Ans));
	Ans[T]=0;
	while(flag){
		flag=0;
		for(int i=1;i<=m;++i)
			for(int j=1;j<=n;++j)
				if(cut[i][j]){
					memset(vis,0,sizeof(vis));
					int tmp=dfs(j,i)+1;
					if(Ans[j]>tmp){
						flag=1;
						Ans[j]=tmp;
					}
				}			
	}
	if(Ans[S]>233) Ans[S]=-1;
	printf("%d\n",Ans[S]);
	return 0;
}