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';
}