Thuật toán Floyd tìm đường đi ngắn nhất giữa mọi cặp đỉnh

2017-08-09
Bài gốc

SPOJ FLOYD

Đề bài

Cho đơn đồ thị vô hướng N đỉnh và M cạnh, trọng số các cạnh C đều nguyên dương. Có K câu hỏi thuộc 2 loại: 0 u v : Cho biết đường đi ngắn nhất từ u tới v có độ dài là bao nhiêu. 1 u v : Hãy chỉ ra 1 đường đi ngắn nhất từ u => v.

Giới hạn:

  • 1 ≤ N ≤ 100
  • 1 ≤ M ≤ N*(N-1)/2
  • 1 ≤ K ≤ 1000
  • 1 ≤ C ≤ 10000
Định dạng test

Input:

  • Dòng 1 : 3 số nguyên N , M , K.
  • M dòng tiếp theo , dòng thứ i gồm 3 số nguyên dương u , v , c cho biết cạnh (u,v) có trọng số là c.
  • K dòng tiếp theo là K câu hỏi , dòng thứ j sẽ có định dạng như đã nêu ở trên.

Output:

  • Ứng với mỗi câu hỏi trong K câu hỏi thì ta phải trả lời trên mỗi dòng như sau .
  • Câu hỏi 0 u v : Ghi ra 1 số nguyên duy nhất là độ dài đường đi ngắn nhất từ u -> v.
  • Câu hỏi 1 u v : Ghi ra số đầu tiên là số X là số đỉnh trên đường đi ngắn nhất này , tiếp đó ghi ra X số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình.

Ví dụ:

input:
3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3
---
output:
3
3 1 2 3
Thuật toán

Tìm đường đi ngắn nhất giữa mọi cặp đỉnh sử dụng thuật toán Floyd: gọi w[i][j] là khoảng cách ngắn nhất từ đỉnh i đến j, giá trị khởi tạo:

  • w[i][i] = 0.
  • w[i][j] = c[i][j].
  • w[i][j] = ∞ nếu giữa i và j không có cạnh nối.

Truy vết: gọi trace[i][j] là đỉnh ngay trước j trong đường đi ngắn nhất từ i đến j (i -> trace[i][j] -> j), giá trị khởi tạo:

  • trace[i][j] = i.
Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

const int N = 105;
const ll oo = 1e18;
int n, m, k, trace[N][N];
ll c[N][N];

void tracefnc(int u, int v, vector<int> & path) {
    if (u != v) tracefnc(u, trace[u][v], path);
    path.pb(v);
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;

    // floyd init
    FOR(i,1,n) FOR(j,1,n) c[i][j] = oo;
    FOR(i,1,n) c[i][i] = 0;
    FOR(i,1,n) FOR(j,1,n) trace[i][j] = i;

    // edges
    FOR(i,1,m) {
        int u, v;
        cin >> u >> v >> c[u][v];
        c[v][u] = c[u][v];
    }

    // floyd
    FOR(k,1,n)
    FOR(i,1,n)
    FOR(j,1,n)
    if (c[i][k] + c[k][j] < c[i][j]) {
        c[i][j] = c[i][k] + c[k][j];
        trace[i][j] = trace[k][j];
    }

    FOR(i,1,n)
    FOR(j,1,n)
    if (c[i][j] == oo) trace[i][j] = -1;

    // solve queries
    while(k--) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) cout << c[u][v];
        else {
            if (trace[u][v] == -1) { cout << -1; continue; }

            vector<int> path;
            tracefnc(u, v, path);

            cout << sz(path);
            REP(i,sz(path)) cout << ' ' << path[i];
        }
        if (k) cout << '\n';
    }

    return 0;
}
Độ phức tạp

O(N3 + KN)