Khi Marisa(魔理沙) và Reimu(霊夢) cùng di chuyển thì số cạnh đi được của mỗi người bằng nhau và tổng số cạnh đi được của $2$ ~Zoro~ người là số chẵn.
Để $2$ người sớm gặp nhau nhất có thể thì đường đi họ đi là ngắn nhất và có độ dài là số chẵn.
Do đó, ta sẽ tìm đường đi ngắn nhất từ $a$ đến $b$ mà số cạnh đi qua là chẵn.
Nếu tồn tại thì đáp án bài toán là một nửa độ dài đường đi ngắn nhất đó.
Còn nếu ... ♪*Ta mất nhau thật rồi, em ơi*♪, tức là không có đường đi có số cạnh chẵn nào (bao gồm việc hai vị trí của Marisa và Reimu không được nối với nhau hay có nối nhưng tất cả các đường đều lẻ), thì in ra $-1$;
ℭ𝔬𝔡𝔢 ℭ++:
```
#include <iostream>
#include <vector>
#include <queue>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, m, u, v, x, y;
std::cin>>n>>m>>x>>y;
std::vector<std::vector<int>> a(n + 1), dist(n + 1, std::vector<int>(2, -2));
//dist: Lưu đường đi ngắn nhất kèm trạng thái chẵn lẻ
//Trạng thái 0 là chẵn, 1 là lẻ
//mình để -2 là vì lát nữa đáp là nửa độ dài đường đi thì viết cho gọn (Không nên học theo nha)
for (int i = 0; i<m; ++i) {
std::cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
std::queue<std::pair<int, int>> q;
//Hàng đợi cạnh với tính chẵn lẻ của nó
q.push({x, 0});
dist[x][0] = 0;
while (not q.empty()) {
int u = q.front().first, k = q.front().second;
q.pop();
for (int v : a[u]) {
if (dist[v][1 - k] == -2) {
dist[v][1 - k] = dist[u][k] + 1;
//Mỗi lần thêm 1 cạnh thì thay đổi tính chẵn lẻ
q.push({v, 1 - k});
}
}
}
std::cout<<dist[y][0]/2;
//Độ dài đường đi ngắn nhất từ x đến y có độ dài cạnh là chẵn
//Đáp là nửa độ dài đó
return 0;
}
```
Lưu ý: Khi lấy giá trị pair, tránh viết như thế này:
```
auto [u, k] = q.front();
```
vì code này chỉ chạy ở C++ $17$, cho vào C++ $14$ là lỗi
minhnhatha
Created at
10 likes