Hướng dẫn giải của Đường đi nguyên tố
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Mỗi cạnh trọng số ~w~ muốn dùng được phải tăng lên số nguyên tố nhỏ nhất ~\ge w~, nên chi phí cạnh là ~nxt(w)-w~ (bằng 0 nếu ~w~ đã nguyên tố). Bài toán trở thành tìm đường đi ngắn nhất từ ~s~ đến ~t~ với chi phí cạnh không âm: dùng Dijkstra. Sàng nguyên tố đến ~1000100~ để tính ~nxt~ (số nguyên tố đầu tiên sau ~10^6~ là 1000003).
Sub 1: Dijkstra ~O(n^2)~, dùng khi ~n, m \le 2000~
Mỗi bước chọn đỉnh chưa cố định có khoảng cách nhỏ nhất bằng cách duyệt mảng. Nếu chỉ nộp sub này: đúng 25/31 test.
Sub 2: Dijkstra với hàng đợi ưu tiên — ~O((n+m)\log n)~
Dùng ~priority_queue~ nên chạy được với ~n, m \le 10^5~. Chú ý dùng ~long long~ cho khoảng cách. Đúng 31/31 test.
Chương trình hoàn chỉnh
Hàm main đọc từ file DDNT.inp, tính chi phí cạnh, ~n,m \le 2000~ gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const int MAXP = 1000100;
int n, m, s, t;
vector<pair<int,int>> adj[100005];
int nxt[MAXP]; // nxt[w] = số nguyên tố nhỏ nhất >= w
bool comp[MAXP];
long long dist_[100005];
// Chi phí cạnh trọng số w là nxt[w] - w
void prepare() {
comp[0] = comp[1] = true;
for (int i = 2; (long long)i * i < MAXP; i++)
if (!comp[i]) for (int j = i * i; j < MAXP; j += i) comp[j] = true;
int last = -1;
for (int w = MAXP - 1; w >= 0; w--) {
if (!comp[w]) last = w;
nxt[w] = last;
}
}
// Sub 1: Dijkstra O(n^2) không dùng heap — dùng khi n, m <= 2000
void sub1() {
vector<bool> done(n + 1, false);
fill(dist_, dist_ + n + 1, LLONG_MAX);
dist_[s] = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int v = 1; v <= n; v++)
if (!done[v] && dist_[v] != LLONG_MAX && (u == -1 || dist_[v] < dist_[u])) u = v;
if (u == -1) break;
done[u] = true;
for (auto &e : adj[u])
dist_[e.first] = min(dist_[e.first], dist_[u] + e.second);
}
cout << dist_[t] << "\n";
}
// Sub 2: Dijkstra với hàng đợi ưu tiên O((n+m) log n)
void sub2() {
fill(dist_, dist_ + n + 1, LLONG_MAX);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist_[s] = 0; pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist_[u]) continue;
for (auto &e : adj[u])
if (d + e.second < dist_[e.first]) {
dist_[e.first] = d + e.second;
pq.push({dist_[e.first], e.first});
}
}
cout << dist_[t] << "\n";
}
int main() {
freopen("DDNT.inp", "r", stdin);
freopen("DDNT.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
prepare();
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
int c = nxt[w] - w;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
if (n <= 2000 && m <= 2000) sub1();
else sub2();
return 0;
}
Bình luận