ABC 289 E 题解

Andy2035 · 2023-02-18 13:03:51 · 题解

题目分析

无向无权图的最短路，可以考虑用图上bfs解决，只不过这里需要记录两个人的位置 这题作为E题算是简单的了

C++ Code

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2010;
vector<int> G[N];
int n,m;
int dis[N][N];
int c[N];
bool st[N][N];
bool ok = false;
int bfs(int u,int v){
    st[u][v] = true;
    dis[u][v] = 0;
    queue<pair<int,int>> q;
    q.push({u,v});
    while(!q.empty()){
        auto t = q.front();q.pop();
        int a = t.first,b = t.second;
        if(a==n&&b==1)return dis[a][b];
        for(auto i:G[a]){
            for(auto j:G[b]){
                if(!st[i][j]&&c[i]!=c[j]){
                    st[i][j] = true;
                    dis[i][j] = dis[a][b] + 1;
                    q.push({i,j});
                }
            }
        }
    }
    return -1;
}
void Main(){
    ok = false;
    memset(st,0,sizeof(st));
    memset(G,0,sizeof(G));
    memset(dis,0,sizeof dis);
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>c[i];
    for(int i = 0;i<m;i++){
        int u,v;cin>>u>>v;G[v].pb(u),G[u].pb(v);
    }
    cout<<bfs(1,n)<<endl;
}
int main(){
    int T;cin>>T;
    while(T--){
        Main();
    }
    return 0;
}