Hướng dẫn giải của Khóa đường (KS2)
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
Chọn một cạnh để tăng gấp đôi trọng số; mức tăng lớn nhất của khoảng cách 1 -> N là đáp án (0 nếu không tăng được).
Sub 1: Thử mọi cạnh, ~M \le 2000~ ~O(M \cdot N^2)~
Với mỗi cạnh, tăng gấp đôi trọng số, chạy lại Dijkstra O(N^2) trên ma trận. Chạy riêng subtask này đạt 10/10 test.
Sub 2: Chỉ cạnh trên đường ngắn nhất, ~M \le 10^4~ ~O(M \cdot N^2)~
Cạnh không nằm trên đường ngắn nhất không làm tăng khoảng cách, nên chỉ thử cạnh có d1[u] + w + dN[v] = D. Chạy riêng subtask này đạt 10/10 test.
Chương trình hoàn chỉnh
Nếu M <= 2000 dùng sub 1, ngược lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;
int N, M;
vector<vector<ll>> W; // ma tran trong so (0 = khong co duong noi)
vector<array<ll, 3>> E; // cac canh (u, v, w), dinh danh 0..N-1
// Dijkstra O(N^2) tren ma tran: khoang cach tu s den moi dinh
vector<ll> distFrom(int s) {
vector<ll> d(N, INF);
vector<char> done(N, 0);
d[s] = 0;
for (int it = 0; it < N; it++) {
int u = -1;
for (int v = 0; v < N; v++)
if (!done[v] && d[v] < INF && (u == -1 || d[v] < d[u])) u = v;
if (u == -1) break;
done[u] = 1;
for (int v = 0; v < N; v++)
if (W[u][v] > 0 && d[u] + W[u][v] < d[v]) d[v] = d[u] + W[u][v];
}
return d;
}
// Sub 1: vet can, dung khi M <= 2000: voi moi canh, tang doi do dai roi tinh lai khoang cach 1 -> N
void sub1() {
ll D = distFrom(0)[N - 1];
ll ans = 0;
for (auto& e : E) {
int u = e[0], v = e[1];
ll w = e[2];
W[u][v] = W[v][u] = 2 * w;
ll nd = distFrom(0)[N - 1];
W[u][v] = W[v][u] = w;
ans = max(ans, nd - D);
}
cout << ans << "\n";
}
// Sub 2: chi xet canh nam tren mot duong ngan nhat (d1[u] + w + dN[v] = D); canh khac tang doi khong doi D
void sub2() {
vector<ll> d1 = distFrom(0), dN = distFrom(N - 1);
ll D = d1[N - 1];
ll ans = 0;
for (auto& e : E) {
int u = e[0], v = e[1];
ll w = e[2];
bool onPath = (d1[u] + w + dN[v] == D) || (d1[v] + w + dN[u] == D);
if (!onPath) continue;
W[u][v] = W[v][u] = 2 * w;
ll nd = distFrom(0)[N - 1];
W[u][v] = W[v][u] = w;
ans = max(ans, nd - D);
}
cout << ans << "\n";
}
int main() {
freopen("RBLOCK.inp", "r", stdin);
freopen("RBLOCK.out", "w", stdout);
cin >> N >> M;
W.assign(N, vector<ll>(N, 0));
E.resize(M);
for (int i = 0; i < M; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
u--; v--;
W[u][v] = W[v][u] = w;
E[i] = {u, v, w};
}
if (M <= 2000) sub1();
else sub2();
return 0;
}
Bình luận