[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;

}