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
#**HƯỚNG DẪN:**<br>
- Giả sử $k$ là vị trí để $a,b$ gặp nhau với độ dài đường đi ngắn nhất.<br>
- Gọi $lena,lenb$ là độ dài đường đi ngắn nhất từ $a,b$ tới $k.$ (ta chỉ biết được đường đi ngắn nhất nên sẽ từ đó biến đổi để thành đường đi đáp án)<br>
Ta có mô hình đường đi ngắn nhất của riêng $a\rightarrow k$ và $k\rightarrow b.$<br>
$a\rightarrow a1\rightarrow a2\rightarrow ...\rightarrow a(lena-1)\rightarrow k\rightarrow b(lenb-1)\rightarrow ...\rightarrow b2\rightarrow b1\rightarrow b$<br>
- Gỉa sử $lena>=lenb.$ Khi đó để $a,b$ đi theo $1$ đường nào đó tới $k$ sẽ mất thời gian $>=lena$(do $lena$ là độ dài ngắn nhất)<br>
$+$ Nếu $lena-lenb>=2:$<br>
Ta xét $len1a,len1b$ là độ dài đường ngắn nhất $a$ tới $a(lena-1).$ Và đường ngắn nhất từ $b\rightarrow k\rightarrow a(lena-1)$ Ta có các tính chất:<br>
$len1a-len1b$ cùng tính chẵn lẻ với $lena-lenb.(len1a=lena-1,len1b=lenb+1)$
Nếu $len1a-len1b$ chẵn thì ta đi đường $len1b$ rồi lặp lại $k\rightarrow a(lena-1)\rightarrow k\rightarrow a(lena-1)\rightarrow ...$<br>
Nếu $len1a-len1b$ lẻ thì ta đi $a->a(lena-1)$ như lúc đi $lena$ và $b\rightarrow k$ như lúc đi $lenb$ cùng với việc thay $a(lena-1)\rightarrow k$ thành $k\rightarrow a(lena-1)$ (đường đi của $b$)<br>
$\rightarrow$ Ta chứng minh được trường hợp này luôn tồn tại $1$ đường đi ngắn hơn hoặc bằng đường tới $k$ và $a,b$ tới $1$ điểm khác $k.$ Nên trường hợp này vô lý hoặc có thể thay thế bằng điểm thỏa mãn trường hợp còn lại.<br>
$+$ Nếu $lena=lenb$ thì lấy còn $lena=lenb+1$ thì ta cần tìm xem có tồn tại $1$ đường đi độ dài $lena+1$ hoặc $lenb+1$<br>
Ta sẽ biến đổi $BFS$ bình thường thay vì lấy các đường đi ngắn nhất tới các đỉnh thì nếu đường đi tới đỉnh đó $=$ đường ngắn nhất $+1$ cũng dùng để lan ra.(để đi từ $1$ đỉnh tới $1$ đỉnh khác với đường đi hơn đường ngắn nhất $1$ đơn vị thì $1$ trong số đường đi từ đỉnh này qua các đỉnh trong đường đi ngắn nhất phải đổi thành $1$ đường có độ dài hơn đường ngắn nhất tới đỉnh đó $1$ đơn vị)<br>
#**CODE MẪU:**<br>
```cpp
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n,m,a,b,u,v,ans=1000000000;
pair<int,int> dda[100005],ddb[100005];
queue<int> qe;
vector<int> dske[100005];
void bfs(int x,pair<int,int> dd[])
{
for(int i=1;i<=n;i++)
{
dd[i].first=dd[i].second=-1;
}
int pathlen=0,cnt=1,cnt1,frt;
dd[x].first=0;
qe.push(x);
while(cnt)
{
pathlen++;
cnt1=0;
while(cnt--)
{
frt=qe.front();
for(int i:dske[frt])
{
if(dd[i].first==pathlen-1)
{
dd[i].second=pathlen;
qe.push(i);
cnt1++;
}
else if(dd[i].first==-1)
{
dd[i].first=pathlen;
qe.push(i);
cnt1++;
}
}
qe.pop();
}
cnt=cnt1;
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>m;
cin>>a>>b;
while(m--)
{
cin>>u>>v;
dske[u].push_back(v);
dske[v].push_back(u);
}
bfs(a,dda);
bfs(b,ddb);
for(int i=1;i<=n;i++)
{
if(dda[i].first!=-1&&(dda[i].first==ddb[i].first||dda[i].first==ddb[i].second))
{
ans=min(ans,dda[i].first);
}
else if(dda[i].second!=-1&&(dda[i].second==ddb[i].first||dda[i].second==ddb[i].second))
{
ans=min(ans,dda[i].second);
}
}
if(ans!=1000000000) cout<<ans;
else cout<<-1;
}
```
minhnhatha
Created at
40 likes
sharinganvanhoadong
Created at
0 likes