Tóm tắt đề bài : tìm đường đi ngắn nhất của cả Tom và Jerry sao cho dist_Tom >= dist_Jerry vì như vậy Jerry mới có thể chạy thoát khỏi Tom.
Ta dùng thuật toán BFS kiểm tra đường đi ngắn nhất như bình thường, kiểm tra đường đi ngắn nhất từ đỉnh của Tom và cả đỉnh của Jerry
Dùng một biến đếm để kiểm tra số đường đi ngắn nhất mà dist_Tom >= dist_Jerry (Bản thân vị trí ban đầu của Jerry cũng được tính).
Code mẫu :
```
#include <bits/stdc++.h>
#define int long long
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define endl "\n"
using namespace std;
const int maxn = 1e5 + 7;
int n, m, a, b;
vector<int> ke[maxn];
int d_tom[maxn], d_jerry[maxn];
queue<int> q;
void bfs(int s, int d[]) {
fill(d, d + n + 1, -1);
q.push(s);
d[s] = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int v : ke[u]) {
if(d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
}
void solve() {
cin >> n >> m;
cin >> a >> b;
for(int i=1;i<=m;++i) {
int u, v; cin >> u >> v;
ke[u].push_back(v);
ke[v].push_back(u);
}
bfs(a, d_jerry);
bfs(b, d_tom);
int nt = 0;
for(int i=1;i<=n;++i) {
if(d_jerry[i] <= d_tom[i]) {
nt++;
}
}
cout << nt << endl;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
cerr << "Time elapsed : " << TIME << "s.\n";
return 0;
}
remydafrog
Created at
1 likes