D. Graph and Graph
You are given two connected undirected graphs with the same number of vertices. In both graphs, there is a token located at some vertex. In the first graph, the token is initially at vertex $s_1$, and in the second graph, the token is initially at vertex $s_2$. The following operation is repeated an infinite number of times:
- Let the token currently be at vertex $v_1$ in the first graph and at vertex $v_2$ in the second graph.
- A vertex $u_1$, adjacent to $v_1$, is chosen in the first graph.
- A vertex $u_2$, adjacent to $v_2$, is chosen in the second graph.
- The tokens are moved to the chosen vertices: in the first graph, the token moves from $v_1$ to $u_1$, and in the second graph, from $v_2$ to $u_2$.
- The cost of such an operation is equal to $|u_1 - u_2|$.
Determine the minimum possible total cost of all operations or report that this value will be infinitely large.
Input
Each test consists of multiple test cases. The first line contains one integer $t$ ($1 \le t \le 500$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains three integers $n$, $s_1$, and $s_2$ ($2 \le n \le 1000$, $1 \le s_1, s_2 \le n$) — the number of vertices in each graph, the number of the vertex in the first graph where the token is initially located, and the number of the vertex in the second graph where the token is initially located.
The second line of each test case contains one integer $m_1$ ($1 \le m_1 \le 1000$) — the number of edges in the first graph.
The $i$-th of the following $m_1$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$) — the numbers of the endpoints of the $i$-th edge in the first graph.
The next line of each test case contains one integer $m_2$ ($1 \le m_2 \le 1000$) — the number of edges in the second graph.
The $j$-th of the following $m_2$ lines contains two integers $c_j$ and $d_j$ ($1 \le c_j, d_j \le n$, $c_j \ne d_j$) — the numbers of the endpoints of the $j$-th edge in the second graph.
It is guaranteed that the sum of $n$, the sum of $m_1$, and the sum of $m_2$ over all test cases do not exceed $1000$.
It is guaranteed that both graphs are connected.
题解
数据范围n^2
用二维的dij
struct node {
int v0,v1,tot;
bool operator< (const node& b) const {
return tot > b.tot;
};
};
优先队列重载只能用<
然后用cosnt修饰operator<，
按引用传递const node& b速度会快一点
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
void solve() {
int n, s1, s2;
cin >> n >> s1 >> s2;
vector<vector<vector<int>>> G(2,vector<vector<int>>(n+1));
int m1;
cin >> m1;
for (int i = 1; i <= m1; i++) {
int u, v;
cin >> u >> v;
G[0][u].push_back(v);
G[0][v].push_back(u);
}
int m2;
cin >> m2;
for (int i = 1; i <= m2; i++) {
int u, v;
cin >> u >> v;
G[1][u].push_back(v);
G[1][v].push_back(u);
}
vector<vector<int>> M(n+1,vector<int>(n+1));
vector<bool> f(n+1,false);
bool ex = true;
for (int i = 1; i <= n; i++) {
unordered_map<int, bool> mp;
for (auto j : G[0][i]) {
mp[j] = true;
}
for (auto j : G[1][i]) {
if (mp.find(j) != mp.end()) {
f[i] = true;
f[j] = true;
ex = false;
}
}
}
if (ex) {
cout << -1 << "\n";
return;
}
struct node {
int v0,v1,tot;
bool operator< (const node& b) const {
return tot > b.tot;
};
};
priority_queue<node> q;
vector<vector<int>> dis(n+1,vector<int>(n+1));
vector<vector<bool>> vis(n+1,vector(n+1,false));
const int inf = 1e9;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = inf;
}
}
dis[s1][s2] = 0;
q.push({s1,s2,0});
while(q.size()) {
node tp = q.top();
q.pop();
if (vis[tp.v0][tp.v1]) continue;
vis[tp.v0][tp.v1] = 1;
for (auto i : G[0][tp.v0]) {
for (auto j : G[1][tp.v1]) {
if (tp.tot + abs(i-j) < dis[i][j]) {
dis[i][j] = tp.tot + abs(i-j);
q.push({i,j,dis[i][j]});
}
}
}
}
int ans = inf;
for (int i = 1; i <= n; i++) {
if (!f[i]) continue;
ans = min(ans,dis[i][i]);
}
cout << (ans == inf ? -1 : ans)<< "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while(T--) {
solve();
}
return 0;
}