Shortest Paths

Dijkstra

Giữ $d_v$ là độ dài đường tốt nhất đã biết từ nguồn tới $v$, ban đầu $d_s = 0$, còn lại $\infty$. Nới lỏng cạnh $u \to v$ dài $w$: nếu $d_u + w < d_v$ thì gán $d_v = d_u + w$. Dijkstra lặp: lấy đỉnh chưa chốt có $d$ nhỏ nhất, chốt nó, rồi nới mọi cạnh đi ra.

Vì sao đỉnh có $d$ nhỏ nhất đã đúng? Mọi đường tới nó phải rời tập đã chốt qua một cạnh nào đó tới một đỉnh chưa chốt có $d$ ít nhất bằng nó, và phần đường còn lại có độ dài không âm. Lập luận này hỏng khi có cạnh âm: một đường vòng qua cạnh âm có thể quay lại rẻ hơn.

Cài bằng priority_queue các cặp $(d, v)$ nhỏ nhất trước. Không cần thao tác “giảm khóa”: mỗi lần nới thành công thì đẩy cặp mới, và khi lấy ra một cặp có $d$ lớn hơn $d_v$ hiện tại thì bỏ qua. Mỗi cạnh đẩy tối đa một cặp, nên hàng đợi có $O(m)$ phần tử, tổng $O(m \log m)$. Độ dài tới $10^9$ và đường tới $10^5$ cạnh cho tổng tới $10^{14}$: dùng ll và $\infty = 10^{18}$.

priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, s});
while (!pq.empty()) {
    ll du = pq.top().first, u = pq.top().second;
    pq.pop();
    if (du > d[u]) continue;
    for (pair<ll, ll> e : g[u])
        if (du + e.second < d[e.first]) {
            d[e.first] = du + e.second;
            pq.push({d[e.first], e.first});
        }
}

Ví dụKhoảng Cách Từ Đỉnh Đầu

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh dài tới $10^9$ (có khuyên và cạnh lặp). In khoảng cách ngắn nhất từ 1 tới mọi đỉnh.

Lời giải. Dijkstra đúng như khung trên. Khuyên và cạnh lặp không cần xử lý riêng: khuyên không bao giờ nới thành công, cạnh lặp chỉ là thêm một lựa chọn.

Bước 1: hàng đợi ưu tiên nhỏ nhất. pq chứa cặp (khoảng cách, đỉnh), greater làm phần tử nhỏ nhất nằm trên đỉnh. INF = 1e18 lớn hơn mọi khoảng cách thật ($10^5 \cdot 10^9$).

for (ll i = 1; i <= n; i++) d[i] = INF;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
d[1] = 0;
pq.push({0, 1});

Bước 2: lấy ra và nới. C++ không có thao tác “giảm khóa”, nên nới được thì đẩy thêm một cặp mới; cặp cũ vẫn nằm trong hàng, và khi lấy ra mà du > d[u] thì nó đã lỗi thời, bỏ qua. Lần đầu một đỉnh được lấy ra với du == d[u], khoảng cách đó đã cuối cùng: mọi đường khác phải đi qua một đỉnh chưa lấy ra, có nhãn không nhỏ hơn, và cạnh không âm chỉ làm dài thêm.

while (!pq.empty()) {
    ll du = pq.top().first, u = pq.top().second;
    pq.pop();
    if (du > d[u]) continue;
    for (pair<ll, ll> e : g[u])
        if (du + e.second < d[e.first]) {
            d[e.first] = du + e.second;
            pq.push({d[e.first], e.first});
        }
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, INF = 1e18;
ll n, m, d[N];
vector<pair<ll, ll>> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for (ll i = 1; i <= n; i++) d[i] = INF;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    d[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        ll du = pq.top().first, u = pq.top().second;
        pq.pop();
        if (du > d[u]) continue;
        for (pair<ll, ll> e : g[u])
            if (du + e.second < d[e.first]) {
                d[e.first] = du + e.second;
                pq.push({d[e.first], e.first});
            }
    }
    for (ll i = 1; i <= n; i++) cout << d[i] << ' ';
    cout << '\n';
}

Input5 8
1 2 7
1 3 2
3 2 1
2 4 4
3 4 8
4 5 3
3 5 20
2 5 10

Output0 3 2 7 10

Mỗi cạnh đẩy tối đa một cặp: $O(m \log m)$.

Thông tin phụ trên đường ngắn nhất

Các cạnh $u \to v$ thỏa $d_u + w = d_v$ tạo thành đồ thị đường ngắn nhất: một DAG, vì $d$ tăng ngặt dọc mỗi cạnh khi $w > 0$. Mọi đường ngắn nhất đều đi trên DAG đó, nên đếm số đường, số cạnh ít nhất hay nhiều nhất trên các đường ngắn nhất là quy hoạch động trên DAG (bài 32). Dijkstra lấy đỉnh theo $d$ tăng dần, chính là một thứ tự tô pô của DAG này, nên làm luôn trong lúc nới: nới tốt hơn thì đặt lại thông tin phụ của $v$ theo $u$; nới bằng thì gộp thêm.

Ví dụHồ Sơ Đường Đi Ngắn Nhất

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh dương. In chi phí nhỏ nhất từ 1 tới $n$, số đường đạt chi phí đó (modulo $10^9 + 7$), số cạnh ít nhất và nhiều nhất trên các đường đó.

Lời giải. Kèm theo $d_v$ ba mảng: cnt là số đường ngắn nhất, mn, mx là số cạnh ít nhất, nhiều nhất trên các đường đó. Đỉnh 1 có cnt = 1, hai mảng kia 0. Vì sao đủ: cạnh dương nên mọi $u$ có $d_u + w = d_v$ đều có $d_u < d_v$ và được lấy ra trước $v$. Khi $v$ được lấy ra, mọi đóng góp đã gộp xong, và chỉ lúc đó $v$ mới đẩy thông tin đi tiếp.

Bước 1: khung Dijkstra như ví dụ trước, thêm cnt[1] = 1.

Bước 2: nới với hai trường hợp. Nới tốt hơn: đường cũ tới $v$ không còn ngắn nhất, đặt lại cả ba mảng theo $u$. Nới bằng: thêm một nhóm đường ngắn nhất đi qua $u$, cộng cnt và cập nhật min, max.

ll v = e.first, nd = du + e.second;
if (nd < d[v]) {
    d[v] = nd;
    cnt[v] = cnt[u];
    mn[v] = mn[u] + 1;
    mx[v] = mx[u] + 1;
    pq.push({nd, v});
} else if (nd == d[v]) {
    cnt[v] = (cnt[v] + cnt[u]) % MOD;
    mn[v] = min(mn[v], mn[u] + 1);
    mx[v] = max(mx[v], mx[u] + 1);
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, INF = 1e18, MOD = 1e9 + 7;
ll n, m, d[N], cnt[N], mn[N], mx[N];
vector<pair<ll, ll>> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for (ll i = 1; i <= n; i++) d[i] = INF;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    d[1] = 0;
    cnt[1] = 1;
    pq.push({0, 1});
    while (!pq.empty()) {
        ll du = pq.top().first, u = pq.top().second;
        pq.pop();
        if (du > d[u]) continue;
        for (pair<ll, ll> e : g[u]) {
            ll v = e.first, nd = du + e.second;
            if (nd < d[v]) {
                d[v] = nd;
                cnt[v] = cnt[u];
                mn[v] = mn[u] + 1;
                mx[v] = mx[u] + 1;
                pq.push({nd, v});
            } else if (nd == d[v]) {
                cnt[v] = (cnt[v] + cnt[u]) % MOD;
                mn[v] = min(mn[v], mn[u] + 1);
                mx[v] = max(mx[v], mx[u] + 1);
            }
        }
    }
    cout << d[n] << ' ' << cnt[n] << ' ' << mn[n] << ' ' << mx[n] << '\n';
}

Input5 7
1 5 8
1 2 2
2 5 6
1 3 1
3 4 2
4 5 5
2 4 1

Output8 4 1 3

$O(m \log m)$ như Dijkstra thường.

Trạng thái và nguồn ảo

Mở rộng đỉnh. Khi đường đi có thêm một điều kiện hữu hạn (đã dùng phiếu chưa, đang cầm xe nào, đã qua bao nhiêu cạnh đặc biệt), đỉnh mới là cặp (đỉnh cũ, trạng thái). Một phiếu giảm giá dùng đúng một lần cho hai bản sao của đồ thị: tầng 0 chưa dùng, tầng 1 đã dùng, mỗi cạnh có thêm một bản đi từ tầng 0 lên tầng 1 với giá giảm. Số đỉnh nhân với số trạng thái, thuật toán không đổi.

Nguồn ảo. Câu hỏi “với mọi $i$, giá nhỏ nhất của $a_j + \mathrm{dist}(i, j)$” là Dijkstra từ một đỉnh ảo nối tới mọi $j$ bằng cạnh dài $a_j$, trên đồ thị đảo chiều nếu cạnh có hướng. Không cần thêm đỉnh thật: khởi tạo $d_j = a_j$ và đẩy mọi đỉnh vào hàng đợi.

Ví dụPhiếu Giảm Giá Một Chặng

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ chuyến bay. Phải dùng một phiếu cho đúng một chuyến, chuyến đó chỉ trả $\lfloor c / 2 \rfloor$. Tìm chi phí nhỏ nhất từ 1 tới $n$.

Lời giải. Trạng thái $(v, t)$ với $t$ là đã dùng phiếu chưa. Cạnh $a \to b$ giá $c$ cho ba cạnh: $(a, 0) \to (b, 0)$ giá $c$, $(a, 0) \to (b, 1)$ giá $\lfloor c/2 \rfloor$, $(a, 1) \to (b, 1)$ giá $c$. Dijkstra trên $2n$ trạng thái; đáp án là $d(n, 1)$, vì đề bắt buộc dùng phiếu.

Bước 1: đánh số trạng thái. $(v, t)$ là ô 2 * v + t của một mảng d; đỉnh 1 chưa dùng phiếu là ô 2.

for (ll i = 0; i < 2 * N; i++) d[i] = INF;
d[2] = 0;
pq.push({0, 2});

Bước 2: cạnh sinh tại chỗ. Không cần dựng đồ thị $2n$ đỉnh thật: lấy trạng thái $(u, t)$ ra thì sinh cạnh ngay từ danh sách kề gốc của $u$. Luôn đi được cạnh giá $c$ sang $(v, t)$; nếu chưa dùng phiếu thì thêm lựa chọn giá $\lfloor c/2 \rfloor$ sang $(v, 1)$.

ll u = s / 2, t = s % 2;
for (pair<ll, ll> e : g[u]) {
    ll v = e.first, c = e.second;
    if (du + c < d[2 * v + t]) {
        d[2 * v + t] = du + c;
        pq.push({d[2 * v + t], 2 * v + t});
    }
    if (!t && du + c / 2 < d[2 * v + 1]) {
        d[2 * v + 1] = du + c / 2;
        pq.push({d[2 * v + 1], 2 * v + 1});
    }
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, INF = 1e18;
ll n, m, d[2 * N];
vector<pair<ll, ll>> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for (ll i = 0; i < 2 * N; i++) d[i] = INF;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    d[2] = 0;
    pq.push({0, 2});
    while (!pq.empty()) {
        ll du = pq.top().first, s = pq.top().second;
        pq.pop();
        if (du > d[s]) continue;
        ll u = s / 2, t = s % 2;
        for (pair<ll, ll> e : g[u]) {
            ll v = e.first, c = e.second;
            if (du + c < d[2 * v + t]) {
                d[2 * v + t] = du + c;
                pq.push({d[2 * v + t], 2 * v + t});
            }
            if (!t && du + c / 2 < d[2 * v + 1]) {
                d[2 * v + 1] = du + c / 2;
                pq.push({d[2 * v + 1], 2 * v + 1});
            }
        }
    }
    cout << d[2 * n + 1] << '\n';
}

Input4 5
1 2 8
2 4 7
1 3 5
3 4 10
2 3 1

Output10

Đồ thị trạng thái có $2n$ đỉnh và $3m$ cạnh: $O(m \log m)$.

Ví dụChi Phí Kết Thúc Tối Ưu

Đề. Đồ thị vô hướng $n \le 2 \cdot 10^5$ đỉnh, cạnh dài tới $10^{12}$, đỉnh $j$ có phí $a_j$. Với mỗi $i$, tìm $\min_j (a_j + 2 \cdot \mathrm{dist}(i, j))$.

Lời giải. Thêm một nguồn ảo nối tới mọi $j$ bằng cạnh dài $a_j$, và nhân đôi độ dài mỗi cạnh thật vì đi tới $j$ rồi quay về tốn $2 \cdot \mathrm{dist}$. Khi đó khoảng cách từ nguồn ảo tới $i$ chính là $\min_j (a_j + 2\,\mathrm{dist}(j, i))$. Đồ thị vô hướng nên $\mathrm{dist}(i, j) = \mathrm{dist}(j, i)$, không cần đảo chiều.

Bước 1: nhân đôi cạnh khi đọc.

g[u].push_back({v, 2 * w});
g[v].push_back({u, 2 * w});

Bước 2: nguồn ảo không cần thêm đỉnh. Khởi tạo d[i] = a_i và đẩy mọi đỉnh vào hàng: đúng trạng thái ngay sau khi lấy nguồn ảo ra và nới mọi cạnh của nó. Mọi đỉnh đều có nhãn ban đầu hữu hạn nên không cần $\infty$.

for (ll i = 1; i <= n; i++) {
    cin >> d[i];
    pq.push({d[i], i});
}

Phần còn lại là Dijkstra thường. Giá trị tới khoảng $4 \cdot 10^{17}$, vẫn vừa ll.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 2e5 + 5;
ll n, m, d[N];
vector<pair<ll, ll>> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, 2 * w});
        g[v].push_back({u, 2 * w});
    }
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    for (ll i = 1; i <= n; i++) {
        cin >> d[i];
        pq.push({d[i], i});
    }
    while (!pq.empty()) {
        ll du = pq.top().first, u = pq.top().second;
        pq.pop();
        if (du > d[u]) continue;
        for (pair<ll, ll> e : g[u])
            if (du + e.second < d[e.first]) {
                d[e.first] = du + e.second;
                pq.push({d[e.first], e.first});
            }
    }
    for (ll i = 1; i <= n; i++) cout << d[i] << ' ';
    cout << '\n';
}

Input5 4
1 2 3
2 3 4
3 4 2
1 4 20
30 17 5 40 9

Output19 13 5 9 9

Một lần Dijkstra: $O((n + m) \log n)$.

BFS 0-1

Khi mọi cạnh dài 0 hoặc 1, không cần hàng đợi ưu tiên. Dùng một hàng đợi hai đầu: nới thành công qua cạnh 0 thì đẩy vào đầu, qua cạnh 1 thì đẩy vào cuối. Hàng đợi luôn chứa các đỉnh có $d$ bằng $k$ ở phía trước và $k + 1$ ở phía sau, giống BFS theo lớp, nên lấy ra từ đầu luôn là đỉnh nhỏ nhất. Một đỉnh có thể vào hàng nhiều lần, nhưng như Dijkstra, bỏ qua lần lấy ra cũ. Tổng $O(n + m)$.

Ví dụMê Cung Hai Kiểu Di Chuyển

Đề. Lưới $h, w \le 1000$ có tường. Đi bộ sang ô kề cạnh miễn phí; dịch chuyển tới một ô trống trong hình vuông $5 \times 5$ quanh mình tốn 1 phép. Tìm số phép ít nhất từ ô đầu tới ô đích, hoặc $-1$.

Lời giải. Mỗi ô là một đỉnh; bốn ô kề cạnh nối bằng cạnh 0 (đi bộ), các ô trong hình vuông $5 \times 5$ nối bằng cạnh 1 (dịch chuyển). Trọng số chỉ là 0 hoặc 1 nên dùng BFS 0-1: hàng đợi hai đầu, cạnh 0 đẩy vào đầu, cạnh 1 đẩy vào cuối. Hàng đợi luôn có dạng “các ô khoảng cách $k$, rồi các ô $k + 1$”, nên lấy ra từ đầu luôn là ô nhỏ nhất, như Dijkstra mà không cần heap.

Bước 1: khởi tạo. Lưới đánh số từ 1 nhờ thêm một ký tự đệm; d khởi tạo INF, ô xuất phát 0.

for (ll i = 1; i <= h; i++) {
    cin >> s[i];
    s[i] = " " + s[i];
    for (ll j = 1; j <= w; j++) d[i][j] = INF;
}

Bước 2: đi bộ, cạnh 0. Nới được thì đẩy vào đầu, vì ô đó cùng khoảng cách với ô hiện tại.

for (ll k = 0; k < 4; k++) {
    ll nx = x + dx[k], ny = y + dy[k];
    if (nx < 1 || ny < 1 || nx > h || ny > w || s[nx][ny] == '#') continue;
    if (d[x][y] < d[nx][ny]) {
        d[nx][ny] = d[x][y];
        dq.push_front({nx, ny});
    }
}

Bước 3: dịch chuyển, cạnh 1. Duyệt hình vuông $5 \times 5$ quanh ô, nới được thì đẩy vào cuối.

for (ll nx = x - 2; nx <= x + 2; nx++)
    for (ll ny = y - 2; ny <= y + 2; ny++) {
        if (nx < 1 || ny < 1 || nx > h || ny > w || s[nx][ny] == '#') continue;
        if (d[x][y] + 1 < d[nx][ny]) {
            d[nx][ny] = d[x][y] + 1;
            dq.push_back({nx, ny});
        }
    }

Một ô có thể vào hàng nhiều lần; lần lấy ra thứ hai chỉ nới lại với nhãn đã đúng, không làm sai.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1005, INF = 1e18;
ll h, w, d[N][N];
ll dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string s[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll sr, sc, tr, tc;
    cin >> h >> w >> sr >> sc >> tr >> tc;
    for (ll i = 1; i <= h; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
        for (ll j = 1; j <= w; j++) d[i][j] = INF;
    }
    deque<pair<ll, ll>> dq;
    d[sr][sc] = 0;
    dq.push_back({sr, sc});
    while (!dq.empty()) {
        ll x = dq.front().first, y = dq.front().second;
        dq.pop_front();
        for (ll k = 0; k < 4; k++) {
            ll nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || ny < 1 || nx > h || ny > w || s[nx][ny] == '#') continue;
            if (d[x][y] < d[nx][ny]) {
                d[nx][ny] = d[x][y];
                dq.push_front({nx, ny});
            }
        }
        for (ll nx = x - 2; nx <= x + 2; nx++)
            for (ll ny = y - 2; ny <= y + 2; ny++) {
                if (nx < 1 || ny < 1 || nx > h || ny > w || s[nx][ny] == '#') continue;
                if (d[x][y] + 1 < d[nx][ny]) {
                    d[nx][ny] = d[x][y] + 1;
                    dq.push_back({nx, ny});
                }
            }
    }
    cout << (d[tr][tc] == INF ? -1 : d[tr][tc]) << '\n';
}

Input5 5
1 1
5 5
..#..
..#..
#####
..#..
..#..

Output1

Mỗi ô xét $4 + 24$ hướng: khoảng $3 \cdot 10^7$ bước cho $10^6$ ô.

Floyd-Warshall cho mọi cặp đỉnh

Khi $n$ cỡ vài trăm và cần khoảng cách giữa mọi cặp, Floyd-Warshall gọn nhất: $d_{ij}$ ban đầu là cạnh trực tiếp ngắn nhất, $d_{ii} = 0$; với mỗi $k$ từ 1 tới $n$, thử đi qua $k$: $d_{ij} = \min(d_{ij}, d_{ik} + d_{kj})$. Sau vòng $k$, $d_{ij}$ là đường ngắn nhất chỉ dùng các đỉnh trung gian trong $\{1, \dots, k\}$. Vòng $k$ phải ở ngoài cùng. $O(n^3)$, với $n = 500$ là $1{,}25 \cdot 10^8$ phép đơn giản. Thuật toán cũng chạy được với cạnh âm; có chu trình âm thì một $d_{ii}$ nào đó thành âm.

Ví dụBảng Khoảng Cách

Đề. Đồ thị vô hướng $n \le 500$ đỉnh, có cạnh lặp và khuyên, $q \le 10^5$ câu hỏi khoảng cách giữa hai đỉnh; không có đường thì in $-1$.

Lời giải. $n \le 500$ còn câu hỏi tới $10^5$: tính khoảng cách mọi cặp một lần bằng Floyd-Warshall, mỗi câu hỏi tra bảng.

Bước 1: khởi tạo bảng. $d_{ii} = 0$, còn lại INF. Có cạnh lặp nên chỉ giữ cạnh ngắn nhất giữa mỗi cặp; đồ thị vô hướng nên cập nhật cả hai chiều.

for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
for (ll i = 1; i <= m; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    d[a][b] = min(d[a][b], c);
    d[b][a] = min(d[b][a], c);
}

Bước 2: ba vòng lặp, $k$ ở ngoài cùng. Sau vòng $k$, $d_{ij}$ là đường ngắn nhất chỉ đi qua các đỉnh trung gian trong $1..k$. Dòng continue bỏ cả hàng $i$ khi $i$ chưa tới được $k$: vừa tránh cộng INF + INF tràn số, vừa nhanh hơn.

for (ll k = 1; k <= n; k++)
    for (ll i = 1; i <= n; i++) {
        if (d[i][k] == INF) continue;
        for (ll j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 505, INF = 1e18;
ll n, m, q, d[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
        d[b][a] = min(d[b][a], c);
    }
    for (ll k = 1; k <= n; k++)
        for (ll i = 1; i <= n; i++) {
            if (d[i][k] == INF) continue;
            for (ll j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    while (q--) {
        ll a, b;
        cin >> a >> b;
        cout << (d[a][b] == INF ? -1 : d[a][b]) << '\n';
    }
}

+12 dòngInput5 5 6
1 2 8
1 2 3
2 3 4
3 4 2
1 4 20
1 4
4 1
1 5
5 5
2 4
1 2

Output9
9
-1
0
6
3

$500^3 = 1{,}25 \cdot 10^8$ phép, mỗi câu hỏi $O(1)$.

Cạnh âm và Bellman-Ford

Bellman-Ford nới mọi cạnh, lặp $n - 1$ vòng. Một đường ngắn nhất không lặp đỉnh có tối đa $n - 1$ cạnh, và sau vòng thứ $k$ mọi đường ngắn nhất dùng tối đa $k$ cạnh đã đúng, nên $n - 1$ vòng là đủ khi không có chu trình âm. Tổng $O(nm)$. Nếu vòng thứ $n$ vẫn nới được cạnh $u \to v$ thì $v$ tới được từ một chu trình âm; đáp án chỉ không xác định khi chu trình đó vừa tới được từ nguồn vừa tới được đích. Kiểm điều đó bằng hai lần BFS: từ nguồn trên đồ thị gốc và từ đích trên đồ thị ngược.

Bài lớn nhất đổi dấu mọi trọng số, hoặc giữ nguyên và nới theo chiều tăng: chu trình dương làm điểm tăng vô hạn.

Ví dụĐiểm Số Trên Hành Trình

Đề. Đồ thị có hướng $n \le 2500$ đỉnh, $m \le 5000$ cạnh có điểm $-10^9..10^9$. Tìm tổng điểm lớn nhất từ 1 tới $n$, đi lại cạnh tùy ý; điểm không bị chặn thì in $-1$.

Lời giải. Bellman-Ford theo chiều lớn nhất. Điểm không bị chặn khi có một chu trình dương vừa tới được từ 1, vừa đi tiếp tới được $n$. Sau $n - 1$ vòng nới, một cạnh $a \to b$ còn tăng được $d_b$ nghĩa là $b$ nằm sau một chu trình dương tới được từ 1; nếu thêm $b$ tới được $n$ thì đi vòng chu trình bao nhiêu lần cũng được.

Bước 1: đỉnh tới được $n$. BFS trên đồ thị ngược từ $n$ đánh dấu ok[v].

queue<ll> q;
q.push(n);
ok[n] = 1;
while (!q.empty()) {
    ll u = q.front();
    q.pop();
    for (ll v : rg[u])
        if (!ok[v]) {
            ok[v] = 1;
            q.push(v);
        }
}

Bước 2: $n - 1$ vòng nới. d khởi tạo NEG, chỉ nới từ đỉnh đã có giá trị hữu hạn, tức đã tới được từ 1.

for (ll i = 1; i <= n; i++) d[i] = NEG;
d[1] = 0;
for (ll it = 1; it < n; it++)
    for (ll i = 1; i <= m; i++)
        if (d[ea[i]] != NEG) d[eb[i]] = max(d[eb[i]], d[ea[i]] + ex[i]);

Bước 3: vòng kiểm thứ $n$.

for (ll i = 1; i <= m; i++)
    if (d[ea[i]] != NEG && d[ea[i]] + ex[i] > d[eb[i]] && ok[eb[i]]) {
        cout << -1 << '\n';
        return 0;
    }

NEG = -4e18 để cộng một trọng số âm vào $d$ thật (tới khoảng $-2{,}5 \cdot 10^{12}$) vẫn xa giới hạn; không bao giờ cộng vào chính NEG.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 2505, M = 5005, NEG = -4e18;
ll n, m, ea[M], eb[M], ex[M], d[N], ok[N];
vector<ll> rg[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> ea[i] >> eb[i] >> ex[i];
        rg[eb[i]].push_back(ea[i]);
    }
    queue<ll> q;
    q.push(n);
    ok[n] = 1;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : rg[u])
            if (!ok[v]) {
                ok[v] = 1;
                q.push(v);
            }
    }
    for (ll i = 1; i <= n; i++) d[i] = NEG;
    d[1] = 0;
    for (ll it = 1; it < n; it++)
        for (ll i = 1; i <= m; i++)
            if (d[ea[i]] != NEG) d[eb[i]] = max(d[eb[i]], d[ea[i]] + ex[i]);
    for (ll i = 1; i <= m; i++)
        if (d[ea[i]] != NEG && d[ea[i]] + ex[i] > d[eb[i]] && ok[eb[i]]) {
            cout << -1 << '\n';
            return 0;
        }
    cout << d[n] << '\n';
}

Input4 5
1 2 4
2 4 -1
1 3 -2
3 4 8
2 3 1

Output13

$O(nm) \approx 1{,}25 \cdot 10^7$.