最短路问题

Problem - D - Codeforces（最短路，反向bfs）

题目：

思路：

bfs版本：参考自Codeforces Round 1002 (Div. 2) A - D - 知乎

代码：

dijstra：

void solve()
{
    int n;
    cin>>n;
    int s1, s2;
    cin>>s1>>s2;
    s1--, s2--;
    vector<vector<int>> adj1(n), adj2(n);
    int m1, m2;
    cin>>m1;
    vector<PII> edj1(m1);
    for(int i=0, u, v; i<m1; i++){
        cin>>u>>v;
        u--, v--;
        if(u>v) swap(u,v);
        edj1[i]={u,v};
        adj1[u].emplace_back(v);
        adj1[v].emplace_back(u);
    }
    cin>>m2;
    vector<PII> edj2(m2);
    for(int i=0, u, v; i<m2; i++){
        cin>>u>>v;
        u--, v--;
        if(u>v) swap(u,v);
        edj2[i]={u,v};
        adj2[u].emplace_back(v);
        adj2[v].emplace_back(u);
    }
    vector<vector<int>> d(n,vector<int>(n,1e9+7));
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> q;
    for(auto [u1,v1]:edj1){
        for(auto [u2,v2]:edj2){
            if(u1==u2 && v1==v2){
                q.push({0,u1,u1});
            }
        }
    }
    vector<vector<bool>> vis(n,vector<bool>(n, false));
    int res=-1;
    while(!q.empty()){
        auto [d, u1, u2]=q.top();
        q.pop();
        if(vis[u1][u2]) continue;
        vis[u1][u2]=true;
        if(u1== s1 && u2== s2){
            res=d;
        }
        d+=abs(u1-u2);
        for(auto v1:adj1[u1]){
            for(auto v2: adj2[u2]){
                q.push({d,v1,v2});
            }
        }
    }
    cout<<res<<'\n';
}

反向bfs： 

void solve()
{
    int n;
    cin>>n;
    int s1, s2;
    cin>>s1>>s2;
    s1--, s2--;
    vector<vector<int>> adj1(n), adj2(n);
    int m1, m2;
    cin>>m1;
    for(int i=0, u, v; i<m1; i++){
        cin>>u>>v;
        u--, v--;
        if(u>v) swap(u,v);
        adj1[u].emplace_back(v);
        adj1[v].emplace_back(u);
    }
    cin>>m2;
    for(int i=0, u, v; i<m2; i++){
        cin>>u>>v;
        u--, v--;
        if(u>v) swap(u,v);
        adj2[u].emplace_back(v);
        adj2[v].emplace_back(u);
    }
    vector<vector<int>> dis(n,vector<int>(n,-1));
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> q;
    q.push({0,s1,s2});
    int res=-1;
    while(!q.empty()){
        auto [d,u1,u2]=q.top();
        q.pop();
        if(dis[u1][u2]!=-1) continue;
        dis[u1][u2]=d;

        for(int v1:adj1[u1]){
            for(int v2:adj2[u2]){
                if(u1==u2 && v1==v2){
                    res=d;
                    cout<<res<<'\n';
                    return;
                }
                q.push({d+abs(v1-v2),v1,v2});
            }
        }
    }
    cout<<res<<'\n';
}