k đường đi ngắn nhất
Tìm độ dài k đường đi ngắn nhất từ s tới t: Dijkstra cho mỗi đỉnh lấy ra tối đa k lần, A*, thuật toán Eppstein với heap trái bền vững trong O(m log m + k log k), quy hoạch động top-k trên DAG và thuật toán Yen cho đường đi đơn.
Bài toán đường đi ngắn nhất (k shortest paths) hỏi: trên đồ thị có trọng số không âm, liệt kê độ dài của đường đi rẻ nhất từ tới (không chỉ đường ngắn nhất như Dijkstra). Liệt kê hết mọi đường đi là bất khả thi vì số đường có thể vô hạn (đồ thị có chu trình) hoặc mũ theo . Trang này trình bày ba cách cho phiên bản cho phép lặp đỉnh (walk): Dijkstra cho mỗi đỉnh được lấy ra tối đa lần trong , tăng tốc bằng A*, và thuật toán Eppstein trong dùng heap bền vững. Cuối trang là quy hoạch động "danh sách top-" trên DAG và thuật toán Yen cho phiên bản đường đi đơn (không lặp đỉnh).
Hai phiên bản của bài toán
| Đường đi cho phép lặp (walk) | Đường đi đơn (simple path) | |
|---|---|---|
| Được đi qua một đỉnh nhiều lần? | Có | Không |
| Hai đường khác nhau khi | Dãy cạnh khác nhau | Dãy đỉnh (cạnh) khác nhau |
| Thuật toán | lần Dijkstra, A*, Eppstein | Yen |
| Độ phức tạp điển hình |
Đề thi lập trình hầu hết hỏi phiên bản walk (ví dụ "các chuyến bay có thể đi qua một thành phố nhiều lần"). Đọc kỹ đề: hai đường cùng độ dài thường vẫn được tính là hai đường khác nhau, còn bài "đường đi ngắn nhì" đôi khi chỉ xét các độ dài khác nhau.
Ví dụ xuyên suốt trang: đồ thị có hướng đỉnh, tìm các đường đi từ tới .
graph directed weighted 5 8 1 2 2 1 3 1 3 2 1 2 4 2 3 4 4 4 5 1 2 5 5 4 2 1 highlight green 1 highlight red 5
Liệt kê bằng tay, sáu đường rẻ nhất là:
| Thứ tự | Đường đi | Độ dài |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 |
Đường thứ đi vòng một lần: đó là lý do có vô số đường đi, và vì sao không thể "liệt kê hết rồi sắp xếp".
Cách 1: Dijkstra cho mỗi đỉnh lấy ra tối đa lần
Ý tưởng
Dijkstra thường lấy mỗi đỉnh ra khỏi hàng đợi một lần, ở lần đó ta có đường ngắn nhất tới nó. Bây giờ ta đưa vào hàng đợi từng đường đi (biểu diễn bởi cặp (độ dài, đỉnh cuối)), không gộp các đường tới cùng một đỉnh. Mỗi lần lấy ra đường , ta nối thêm mọi cạnh để được các đường .
Vì mọi trọng số không âm, các đường được lấy ra theo thứ tự độ dài không giảm (cùng lý luận với Dijkstra thường). Do đó lần thứ đỉnh được lấy ra chính là đường ngắn thứ từ tới , và các lần lấy ra cho đúng đáp án.
Nếu chỉ có thế thì hàng đợi phình vô hạn. Nhận xét then chốt cho phép cắt tỉa:
Nếu một đường từ tới nằm trong đường ngắn nhất tới và đi qua đỉnh , thì phần đầu của (từ tới ) nằm trong đường ngắn nhất tới .
Chứng minh. Giả sử có ít nhất đường tới ngắn hơn hẳn . Ghép mỗi đường đó với phần đuôi của (từ tới ) được đường khác nhau tới , đều ngắn hơn hẳn , mâu thuẫn với việc nằm trong đường ngắn nhất. (Khi có các đường bằng độ dài, thứ tự giữa chúng là tùy ý nên vẫn chọn được một bộ đường tốt nhất thỏa tính chất trên.)
Vậy mỗi đỉnh chỉ cần được mở rộng ở lần lấy ra đầu tiên; các lần sau bỏ qua. Mỗi đỉnh mở rộng tối đa lần nên tổng số lần đẩy vào hàng đợi không quá .
Ví dụ chạy tay
Chạy với trên đồ thị ví dụ. là số lần đã được lấy ra.
| Bước | Lấy ra | Đường tương ứng | Ghi chú | |
|---|---|---|---|---|
| 1 | đẩy | |||
| 2 | đẩy | |||
| 3 | đẩy | |||
| 4 | đẩy | |||
| 5 | đẩy | |||
| 6 | đẩy | |||
| 7 | đẩy ; từ giờ | |||
| 8 | bỏ qua vì | |||
| 9 | đẩy ; cạnh không đẩy vì | |||
| 10 | đáp án thứ : | |||
| 11 | đáp án thứ : | |||
| 12 | đáp án thứ : , dừng |
(Các phần tử cùng độ dài có thể ra theo thứ tự khác tùy cài đặt hàng đợi; dãy độ dài in ra thì không đổi.) Code chỉ lưu cặp (độ dài, đỉnh), cột "đường tương ứng" chỉ để minh họa. Chạy chương trình bên dưới với được 5 5 6 7 7 8, khớp bảng liệt kê tay.
Cài đặt
Input: dòng đầu ; dòng là cạnh có hướng trọng số . In độ dài đường đi ngắn nhất từ tới ; nếu chỉ có ít hơn đường thì in cho các vị trí còn thiếu.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
vector<vector<pair<int, ll>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v; ll w;
scanf("%d %d %lld", &u, &v, &w);
adj[u].push_back({v, w});
}
int s = 1, t = n;
vector<int> cnt(n + 1, 0); // how many times each vertex was popped
vector<ll> ans;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
pq.push({0, s});
while (!pq.empty() && (int)ans.size() < k) {
auto [d, u] = pq.top(); pq.pop();
if (cnt[u] == k) continue; // u already has its k best walks
cnt[u]++;
if (u == t) ans.push_back(d); // record on POP, not on push
for (auto [v, w] : adj[u])
if (cnt[v] < k) pq.push({d + w, v});
}
while ((int)ans.size() < k) ans.push_back(-1); // fewer than k walks exist
for (int i = 0; i < k; i++) printf("%lld%c", ans[i], i + 1 < k ? ' ' : '\n');
}
import sys, heapq
def main():
data = sys.stdin.buffer.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = int(data[3 + 3*i]), int(data[4 + 3*i]), int(data[5 + 3*i])
adj[u].append((v, w))
s, t = 1, n
cnt = [0] * (n + 1) # how many times each vertex was popped
ans = []
pq = [(0, s)]
while pq and len(ans) < k:
d, u = heapq.heappop(pq)
if cnt[u] == k:
continue # u already has its k best walks
cnt[u] += 1
if u == t:
ans.append(d) # record on pop, not on push
for v, w in adj[u]:
if cnt[v] < k:
heapq.heappush(pq, (d + w, v))
ans += [-1] * (k - len(ans))
print(*ans)
main()
Với input ví dụ (5 8 6 rồi tám cạnh như hình), cả hai chương trình in 5 5 6 7 7 8.
Độ phức tạp
- Thời gian : mỗi đỉnh được mở rộng tối đa lần, mỗi lần duyệt hết cạnh ra của nó, nên tổng số lần đẩy vào hàng đợi (cộng lần đẩy ). Mỗi thao tác hàng đợi tốn .
- Bộ nhớ : hàng đợi có thể chứa tới phần tử.
Cách này rất ngắn và là lựa chọn mặc định khi nhỏ (cỡ đến ). Khi lên tới thì quá lớn, cần Eppstein.
Tăng tốc bằng A* với hàm ước lượng chính xác
Tính trước = khoảng cách ngắn nhất từ tới (chạy Dijkstra từ trên đồ thị ngược). Trong hàng đợi, xếp đường theo khóa thay vì . Đây là thuật toán A* với hàm ước lượng chính xác:
- Với cùng một đỉnh , là hằng số nên các lần lấy ra vẫn theo thứ tự tăng dần, nhận xét "chỉ mở rộng lần đầu" vẫn đúng. Với thì , khóa chính là độ dài.
- Đỉnh có (không tới được ) không bao giờ được đẩy vào. Điều này loại bỏ hẳn những vùng đồ thị vô ích, và nếu không có đường nào tới thì hàng đợi rỗng ngay.
- Đường đi "lệch" khỏi đường ngắn nhất càng ít thì khóa càng nhỏ, nên thuật toán đi thẳng về phía thay vì loang đều mọi hướng.
Chặn trên lý thuyết vẫn là , nhưng trên thực tế nhanh hơn nhiều. Ý tưởng "độ dài thật = khoảng cách ngắn nhất + phần lệch" chính là nền của thuật toán Eppstein.
Cách 2: thuật toán Eppstein
Cây đường đi ngắn nhất và cạnh rẽ nhánh
Chạy Dijkstra từ trên đồ thị ngược, được = khoảng cách ngắn nhất từ tới . Mỗi đỉnh tới được chọn đúng một cạnh thỏa : các cạnh này tạo thành cây đường đi ngắn nhất gốc . Đi từ theo cây là đi đường ngắn nhất tới .
Mọi cạnh còn lại (với ) gọi là cạnh rẽ nhánh (sidetrack), gắn với độ lệch
là chi phí phải trả thêm khi tại , thay vì đi theo cây, ta rẽ sang rồi đi tiếp đường ngắn nhất từ . Với cạnh của cây thì độ lệch bằng .
Mỗi đường đi là một dãy cạnh rẽ nhánh
Xét một đường từ tới . Bỏ các cạnh của cây, giữ lại các cạnh rẽ nhánh theo thứ tự xuất hiện: . Giữa hai cạnh rẽ nhánh liên tiếp, đi theo cây. Cộng các độ lệch dọc , các số hạng triệt tiêu dạng tổng lồng nhau:
Ngược lại, một dãy cạnh rẽ nhánh xác định đúng một đường đi khi và chỉ khi: xuất phát từ một đỉnh trên đường cây , và với mỗi , xuất phát từ một đỉnh trên đường cây từ đầu cuối của tới . Vậy:
Bài toán trở thành: liệt kê dãy cạnh rẽ nhánh hợp lệ có tổng độ lệch nhỏ nhất. Dãy rỗng là đường ngắn nhất, độ dài .
Heap gom cạnh rẽ nhánh dọc đường cây
Gọi là heap nhỏ nhất chứa mọi cạnh rẽ nhánh xuất phát từ các đỉnh trên đường cây , khóa là . Từ định nghĩa:
Nếu sao chép cho từng thì tốn . Dùng heap trái bền vững (persistent leftist heap): phép gộp chỉ đi dọc đường bên phải (dài ) và sao chép các nút trên đường đó thay vì sửa, nên phiên bản cũ vẫn nguyên vẹn và dùng chung phần lớn nút với nó. Đây cùng tư tưởng với segment tree bền vững; xem heap để ôn tính chất heap. Xử lý các đỉnh theo thứ tự tăng dần (thứ tự Dijkstra lấy ra) thì luôn xong trước .
Duyệt các dãy theo thứ tự tổng độ lệch
Mỗi trạng thái là một nút của một heap , biểu diễn một dãy mà cạnh rẽ nhánh cuối cùng là cạnh tại nút ; giá trị trạng thái là độ dài đường đi tương ứng . Từ trạng thái có tối đa ba bước đi tiếp:
- Thay cạnh cuối bằng con trái của trong heap: .
- Thay cạnh cuối bằng con phải : .
- Giữ cạnh cuối, nối thêm cạnh rẽ nhánh nhỏ nhất sau nó: với là đầu cuối của cạnh tại , đi tới gốc của với giá trị .
Trạng thái đầu là gốc của với giá trị . Vì sao đúng:
- Không giảm: heap có tính chất con cha nên bước 1, 2 không làm giảm ; bước 3 cộng thêm . Mọi bước đều không giảm.
- Đầy đủ và không trùng: mỗi dãy hợp lệ đi tới được từ trạng thái đầu bằng đúng một chuỗi bước: với mỗi cạnh , nó nằm ở đúng một nút trong heap tương ứng và đường từ gốc tới nút đó trong cây heap là duy nhất. Vậy các trạng thái tạo thành một cây có cạnh không âm.
Duyệt cây này bằng hàng đợi ưu tiên (giống Dijkstra trên cây) sẽ lấy ra các trạng thái theo thứ tự giá trị không giảm, mỗi trạng thái đúng một lần. Mỗi lần lấy ra đẩy vào tối đa trạng thái, nên lấy lần chỉ tốn .
Ví dụ chạy tay
Trên đồ thị ví dụ, . Dijkstra trên đồ thị ngược:
| Đỉnh | |||||
|---|---|---|---|---|---|
| Cạnh cây |
Đỉnh có hai lựa chọn cùng tốt ( và , đều cho ); cài đặt chọn cạnh tìm thấy trước là . Cây đường đi ngắn nhất (màu xanh) và bốn cạnh rẽ nhánh (màu cam):
graph directed weighted 5 8 1 2 2 1 3 1 3 2 1 2 4 2 3 4 4 4 5 1 2 5 5 4 2 1 highlight green 1-2 3-2 2-4 4-5 highlight orange 1-3 3-4 2-5 4-2 label 1 d=5 label 2 d=3 label 3 d=4 label 4 d=1 label 5 d=0
Độ lệch các cạnh rẽ nhánh :
| Cạnh rẽ nhánh | ||||
|---|---|---|---|---|
Các heap (ghi theo khóa): , , , , . Lưu ý và dùng chung các nút của , không sao chép.
Các đường đi lấy ra theo thứ tự:
| Thứ tự | Dãy cạnh rẽ nhánh | Độ dài | Đường đi |
|---|---|---|---|
| 1 | (rỗng) | ||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 |
Ở dòng 3: sau cạnh ta ở đỉnh , bước "nối thêm" lấy gốc của là cạnh với . Dòng 6 còn hòa với dãy (cũng độ dài ), là đường thứ . Kết quả khớp đúng bảng liệt kê tay ở đầu trang.
Cài đặt
Cùng định dạng input/output như cách 1. Heap trái lưu trong một vector toàn cục, nút là heap rỗng.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;
// Persistent leftist heap: merge copies nodes, old versions stay valid.
struct Node { ll key; int to; int l, r, rk; };
vector<Node> T = {{0, 0, 0, 0, 0}}; // node 0 = empty heap (rk = 0)
int newNode(ll key, int to) { T.push_back({key, to, 0, 0, 1}); return (int)T.size() - 1; }
int merge(int a, int b) {
if (!a || !b) return a | b;
if (T[a].key > T[b].key) swap(a, b);
int c = (int)T.size(); T.push_back(T[a]); // copy root of a
int nr = merge(T[c].r, b); // T may reallocate: use index
T[c].r = nr;
if (T[T[c].l].rk < T[T[c].r].rk) swap(T[c].l, T[c].r);
T[c].rk = T[T[c].r].rk + 1;
return c;
}
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
vector<int> eu(m), ev(m); vector<ll> ew(m);
vector<vector<int>> radj(n + 1); // incoming edges, for Dijkstra from t
for (int i = 0; i < m; i++) {
scanf("%d %d %lld", &eu[i], &ev[i], &ew[i]);
radj[ev[i]].push_back(i);
}
int s = 1, t = n;
// 1) Dijkstra on the reversed graph: dist[v] = shortest v -> t.
vector<ll> dist(n + 1, INF);
vector<int> treeEdge(n + 1, -1), order; // treeEdge[v]: the ONE edge v -> next on the tree
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
dist[t] = 0; pq.push({0, t});
vector<bool> done(n + 1, false);
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
if (done[v]) continue;
done[v] = true; order.push_back(v); // order = increasing dist
for (int e : radj[v]) {
int u = eu[e];
if (d + ew[e] < dist[u]) { dist[u] = d + ew[e]; treeEdge[u] = e; pq.push({dist[u], u}); }
}
}
vector<ll> ans;
if (dist[s] < INF) {
// 2) h[v] = heap of all sidetrack edges on the tree path v -> t.
vector<vector<int>> out(n + 1);
for (int i = 0; i < m; i++) out[eu[i]].push_back(i);
vector<int> h(n + 1, 0);
for (int v : order) { // parent is processed before child
int base = (v == t) ? 0 : h[ev[treeEdge[v]]];
for (int e : out[v]) {
if (e == treeEdge[v] || dist[ev[e]] >= INF) continue;
ll delta = ew[e] + dist[ev[e]] - dist[v]; // extra cost, always >= 0
base = merge(base, newNode(delta, ev[e]));
}
h[v] = base;
}
// 3) Best-first search over "sidetrack sequences".
ans.push_back(dist[s]); // the shortest walk itself
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
if (h[s]) q.push({dist[s] + T[h[s]].key, h[s]});
while (!q.empty() && (int)ans.size() < k) {
auto [c, x] = q.top(); q.pop();
ans.push_back(c);
// replace the last sidetrack by a sibling candidate in the same heap
if (T[x].l) q.push({c - T[x].key + T[T[x].l].key, T[x].l});
if (T[x].r) q.push({c - T[x].key + T[T[x].r].key, T[x].r});
// keep the last sidetrack and append a new one after its head
int y = h[T[x].to];
if (y) q.push({c + T[y].key, y});
}
}
while ((int)ans.size() < k) ans.push_back(-1);
for (int i = 0; i < k; i++) printf("%lld%c", ans[i], i + 1 < k ? ' ' : '\n');
}
Với input ví dụ, chương trình in 5 5 6 7 7 8. Trên đồ thị ngẫu nhiên , , , chương trình chạy khoảng giây.
Độ phức tạp
- Dijkstra ngược: .
- Dựng heap: mỗi cạnh rẽ nhánh được chèn bằng một phép
merge; phép gộp heap trái đi dọc đường bên phải, dài , và tạo nút mới. Tổng thời gian và bộ nhớ. - Liệt kê: lần lấy ra, mỗi lần đẩy tối đa trạng thái, hàng đợi có phần tử: .
- Tổng: thời gian , bộ nhớ .
(Bài báo gốc của Eppstein đạt bằng các cấu trúc tinh vi hơn; phiên bản heap trái ở trên là bản dùng trong thi đấu.)
Trên DAG: quy hoạch động danh sách top-
Khi đồ thị không có chu trình, có cách đơn giản hơn: với mỗi đỉnh , lưu là danh sách (đã sắp xếp) tối đa độ dài nhỏ nhất của các đường từ tới . Duyệt theo thứ tự tô pô:
Đúng vì cùng nhận xét "phần đầu của một đường tốt cũng là đường tốt": một đường trong top- tới có cạnh cuối thì phần trước nó nằm trong top- tới . DAG đảm bảo khi xử lý thì mọi đã xong. Cách này cho phép cạnh âm (Dijkstra thì không) và cũng dùng cho "k đường dài nhất" trên DAG.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
vector<vector<pair<int, ll>>> radj(n + 1); // incoming edges
vector<vector<int>> adj(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v; ll w;
scanf("%d %d %lld", &u, &v, &w);
radj[v].push_back({u, w}); adj[u].push_back(v); indeg[v]++;
}
// Kahn's topological order
vector<int> order, q;
for (int v = 1; v <= n; v++) if (!indeg[v]) q.push_back(v);
for (size_t i = 0; i < q.size(); i++) {
int u = q[i]; order.push_back(u);
for (int v : adj[u]) if (--indeg[v] == 0) q.push_back(v);
}
// L[v] = sorted list of the (at most) k smallest path lengths 1 -> v
vector<vector<ll>> L(n + 1);
for (int v : order) {
vector<ll> cand;
if (v == 1) cand.push_back(0); // the empty path
for (auto [u, w] : radj[v])
for (ll x : L[u]) cand.push_back(x + w);
if ((int)cand.size() > k) {
nth_element(cand.begin(), cand.begin() + k, cand.end());
cand.resize(k); // keep only the k smallest
}
sort(cand.begin(), cand.end());
L[v] = cand;
}
vector<ll> ans = L[n];
while ((int)ans.size() < k) ans.push_back(-1);
for (int i = 0; i < k; i++) printf("%lld%c", ans[i], i + 1 < k ? ' ' : '\n');
}
Độ phức tạp: đỉnh gom ứng viên, nth_element chạy tuyến tính, rồi sắp xếp phần tử: tổng thời gian, bộ nhớ. Nếu chỉ cần đếm hoặc tìm đường thứ theo thứ tự từ điển, ta thay danh sách bằng số đếm (chặn trên ở ) rồi dựng đường từng bước.
Đường đi đơn: thuật toán Yen
Khi đề cấm lặp đỉnh, các cách trên sai (chúng sẽ đếm cả đường đi vòng như đường thứ ở ví dụ). Thuật toán Yen tìm đường đơn ngắn nhất:
- = đường ngắn nhất (Dijkstra).
- Để tìm : với mỗi đỉnh rẽ trên (trừ ), gọi gốc là đoạn từ tới .
- Xóa tạm mọi cạnh mà một đường đã tìm () có cùng gốc rồi đi tiếp bằng cạnh đó.
- Xóa tạm các đỉnh trong gốc (trừ ) để đường mới không lặp đỉnh.
- Dijkstra từ tới trên đồ thị còn lại; nếu có, ghép gốc với đoạn này thành một ứng viên, đưa vào tập ứng viên (bỏ trùng).
- = ứng viên ngắn nhất trong , xóa nó khỏi .
Mỗi lần tìm chạy tối đa lần Dijkstra, nên tổng . Chỉ dùng được với , nhỏ; trong thi đấu phiên bản đường đơn ít gặp hơn hẳn phiên bản walk.
⚠️ Lỗi thường gặp
- Ghi nhận đáp án lúc đẩy vào hàng đợi. Triệu chứng: in ra dãy không tăng dần hoặc sai giá trị. Thứ tự chỉ đúng khi lấy ra; ghi nhận khi pop như code mẫu.
- Dùng mảng
distvà điều kiệnif (d > dist[u]) continuenhư Dijkstra thường. Điều đó gộp mọi đường tới làm một, chỉ còn đường ngắn nhất. Phải đếm và cho phép lấy ra tới lần. - Quên giới hạn lần cho các đỉnh khác . Hàng đợi phình theo cấp số nhân; nếu không có đủ đường tới (hoặc không tới được) thì vòng lặp không dừng trên đồ thị có chu trình. Kiểm tra
cnt[u] == kcho mọi đỉnh. - Gộp các đường cùng độ dài. Ở ví dụ, hai đường độ dài là hai đáp án khác nhau. Ngược lại, bài "đường ngắn nhì" kiểu hẳn thì phải bỏ qua đường trùng độ dài: đọc kỹ đề định nghĩa "khác nhau" là gì.
- Eppstein: loại mọi cạnh có thay vì đúng một cạnh cây. Triệu chứng: thiếu đường (ở ví dụ, có nhưng không phải cạnh cây; bỏ nó thì mất đường thứ ). Lưu chỉ số cạnh cây
treeEdge[v]và chỉ bỏ đúng cạnh đó; cạnh song song cùng trọng số vẫn là cạnh rẽ nhánh. - Eppstein: thêm cạnh đi tới đỉnh không tới được . làm tràn số. Bỏ qua các cạnh đó, và nếu thì không có đường nào.
- Eppstein: giữ tham chiếu
T[c]qua lời gọi đệ quymerge.push_backcó thể cấp phát lại vector, tham chiếu cũ trỏ vào vùng nhớ đã giải phóng. Code mẫu lưu kết quả đệ quy vào biếnnrrồi mới gánT[c].r = nr. - Tràn số. Độ dài đường thứ có thể vượt (ví dụ và đường đi vòng nhiều lần): dùng
long long. - Cạnh âm. Cả lần Dijkstra lẫn Eppstein cần (Eppstein cần ). Với cạnh âm trên DAG dùng quy hoạch động top-; trên đồ thị tổng quát có chu trình âm thì bài toán không xác định.
- . Đường rỗng độ dài được tính là một đường (cả hai code đều đếm nó). Nếu đề không tính đường rỗng, bỏ đáp án đầu tiên.
Bài tập luyện
- Các Tuyến Bay (flightroutes) (Trung bình): đường đi rẻ nhất từ tới , cho phép lặp đỉnh; áp dụng trực tiếp cách lấy mỗi đỉnh ra tối đa lần.
- Đường đi ngắn nhì (thhv14_shortest) (Khó): đường ngắn nhì có độ dài lớn hơn hẳn độ dài ngắn nhất, nên phải lưu hai độ dài khác nhau cho mỗi đỉnh thay vì đếm số lần lấy ra.
- K hành trình ngắn nhất (gr07_kth) (Khó): hành trình rẻ nhất có khuyên, cạnh song song và trường hợp không đủ hành trình (in ); kiểm tra kỹ các bẫy dừng vòng lặp và .
- Chất lượng dịch vụ (voi14_qos) (Rất khó): tìm đường thứ theo thứ tự từ điển trong các đường có độ trễ không vượt ; dùng tới để tính "độ dư", rồi đếm đường trên DAG trạng thái (đỉnh, độ dư) như mục quy hoạch động trên DAG.
Hiện kho bài CTOJ chưa có bài bắt buộc thuật toán Eppstein (với cỡ ); có thể tự kiểm tra cài đặt Eppstein bằng cách nộp lên các bài trên.
Bình luận