E - Swap Places
题链
考虑dp[i][j]表示第一个点到达i点 第二个点到达j点的min
然后bfs即可 时间复杂度为状态数
int dp[2010][2010],n,m,c[2010];//dp[i][j]表示到达(i,j)的min
vector<int>g[2010];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c[i];
g[i].clear();
}
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
dp[i][j]=INF;
}
}
queue<PII>q;
dp[1][n]=0;
q.push({1,n});
while(q.size()){
auto [x,y]=q.front();q.pop();
for(auto nx:g[x]){
for(auto ny:g[y]){
if(dp[nx][ny]>dp[x][y]+1&&c[nx]!=c[ny]){
dp[nx][ny]=min(dp[nx][ny],dp[x][y]+(c[nx]!=c[ny]));
q.push({nx,ny});
}
}
}
}
if(dp[n][1]==INF)cout<<-1<<endl;
else cout<<dp[n][1]<<endl;
}
标签:AtCoder,Beginner,Contest,int,nx,ny,2010,dp
From: https://www.cnblogs.com/ycllz/p/17120778.html