Bin Laden

Nguồn: Codeforces Group Độ khó: Khá Đồ thị Dijkstra

Đề bài

Trùm khủng bố Bin Laden trốn trong 1 căn hầm được đào sâu xuống mặt đất $M$ tầng, mỗi tầng có $N$ phòng. Các phòng được ngăn cách bằng các cửa rất khó phá. Các phòng có cửa xuống phòng ngay phía dưới và 2 phòng ở 2 bên. Từ trên mặt đất có $N$ cửa xuống $N$ phòng tầng $-1$. Bin Laden ở tầng dưới cùng (tầng $-M$) phòng thứ $N$ (phòng ở bên phải nhất). Mỗi cửa được làm bằng một kim loại khác nhau với độ dày khác nhau nên việc phá cửa cần thời gian khác nhau.

Bạn hãy tìm cách đi từ mặt đất xuống phòng của Bin Laden nhanh nhất không hắn thoát mất.

Input

• Dòng 1 ghi $M$ và $N$.
• Dòng 2 đến $2M + 1$: dòng chẵn ghi $N$ số, dòng lẻ ghi $N - 1$ số là chi phí để phá cửa.

Giới hạn

• $1 \le M \le 2222$
• $1 \le N \le 10$
• Chi phí của các cánh cửa thuộc $[0, 1000]$.

Output: ghi ra 1 số là thời gian nhỏ nhất để đến được phòng của Bin Laden.

Sample input

4 2
99 10
1
10 99
1
99 10
1
10 99
1

Sample output

44

Minh hoạ

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Kiến thức cần có: thuật toán Dijkstra

Để giải quyết được bài này đòi hỏi phải biết về thuật toán Dijkstra. Nếu bạn nào chưa biết về nó thì có thể tham khảo tại link này: Đường đi ngắn nhất – VNOI Wiki.

Thì chỉ là dùng Dijkstra cơ bản thôi, nhưng quan trọng là các bạn phải biết từ dữ liệu ban đầu bài cho mà phải mô hình hóa thành dạng đồ thị, rồi từ đó áp dụng Dijkstra trên đồ thị đó.

Mô hình hoá thành đồ thị

Hãy xem hình dưới đây thầy mô hình hóa thành đồ thị nhé, với các số màu đen là các đỉnh của đồ thị và các gạch nối màu đỏ giữa chúng là các cạnh của đồ thị. Và bên cạnh là kết quả đường đi của ví dụ mẫu:

Đánh số 10 đỉnh cho ví dụ mẫu

Đường đi ngắn nhất của ví dụ mẫu

Với ví dụ dữ liệu mẫu đề cho nhé, ta sẽ có 10 đỉnh đánh số từ 1 đến 10 như hình trên, và tụi nó nối với nhau như trên, tức là ta sẽ có danh sách cạnh là (đỉnh – đỉnh : chi phí):

1 – 3 : 992 – 4 : 103 – 4 : 13 – 5 : 104 – 6 : 995 – 6 : 15 – 7 : 996 – 8 : 107 – 8 : 17 – 9 : 108 – 10 : 999 – 10 : 1

Hai đỉnh 1 và 2 ở trên cùng đại diện cho mặt đất (phía trên 2 cửa đi xuống tầng $-1$), mỗi tầng tiếp theo có $N$ đỉnh ứng với $N$ phòng. Tức là ta có số lượng đỉnh:

V = (M + 1) * N

Giờ đây bài toán là: cần tìm đường đi từ một trong số các đỉnh $1, 2, 3, \ldots, N$ để đi đến đỉnh $V$ với chi phí ít nhất.

Mẹo: chạy Dijkstra ngược từ đích

Vậy thì ta sẽ áp dụng thuật toán Dijkstra từ đỉnh $V$ (phòng của Bin Laden) để tìm đường đi ngắn nhất đi đến các đỉnh $1, 2, 3, \ldots, N$. Sau cùng sẽ chọn ra đáp án nhỏ nhất của các dist[1], dist[2], ..., dist[n], thì đó là đáp án bài toán. Vì cửa đi được cả 2 chiều nên đồ thị là vô hướng, đi từ $V$ ngược lên cũng cho cùng chi phí như đi từ mặt đất xuống, mà chỉ cần chạy Dijkstra đúng 1 lần.

Với ví dụ mẫu, đường đi tốt nhất là đi theo đường zigzac: 2 → 4 → 3 → 5 → 6 → 8 → 7 → 9 → 10, tổng chi phí $10 + 1 + 10 + 1 + 10 + 1 + 10 + 1$ $= 44$.

Em nhập số tầng, số phòng và chi phí các cửa rồi bấm Tiếp để xem Dijkstra chạy ngược từ phòng Bin Laden, mỗi bước chốt 1 đỉnh có dist nhỏ nhất:

M N Chi phí (theo thứ tự các dòng)

Ví dụ nhanh:

Các dòng chi phí cách nhau bằng dấu | cho dễ nhìn (dòng có N số là cửa đi xuống, dòng có N − 1 số là cửa ngang).

Cách đọc input để dựng cạnh

Trong code, mình duyệt $i$ từ 1 đến $2M$ (ứng với $2M$ dòng chi phí). Đỉnh bắt đầu của dòng thứ $i$ là u = (i / 2) * n + 1:

• $i$ lẻ (dòng có $N$ số): đây là các cửa đi xuống, nối đỉnh u với đỉnh u + n ngay bên dưới, lần lượt cho $N$ cột.
• $i$ chẵn (dòng có $N - 1$ số): đây là các cửa ngang trong cùng 1 tầng, nối đỉnh u với đỉnh u + 1 bên phải, lần lượt cho $N - 1$ cặp phòng kề nhau.

Mỗi cạnh được thêm vào danh sách kề của cả 2 đỉnh vì đồ thị vô hướng.

Source code

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

#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m, n;
    cin >> m >> n;
    int V = (m + 1) * n;
    vector<vector<pair<int, int>>> graph(V + 1, vector<pair<int, int>>());
    int sz = 2 * m;
    for(int i = 1; i <= sz; ++i){
        int u = (i / 2) * n + 1;
        int v, w;
        if(i % 2 != 0){
            for(int j = 1; j <= n; ++j){
                cin >> w;
                v = u + n;
                graph[u].push_back({v, w});
                graph[v].push_back({u, w});
                u++;
            }
        }
        else{
            v = u + 1;
            for(int j = 1; j < n; ++j){
                cin >> w;
                graph[u].push_back({v, w});
                graph[v].push_back({u, w});
                u++;
                v++;
            }
        }
    }

    int INF = 1e9;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // cost, u
    vector<int> dist(V + 1, INF);
    pq.push({0, V});
    dist[V] = 0;
    while(!pq.empty()){
        pair<int, int> top = pq.top();
        pq.pop();
        int w = top.first;
        int u = top.second;
        if(dist[u] != w){
            continue;
        }
        for(int i = 0; i < graph[u].size(); ++i){
            pair<int, int> neighbor = graph[u][i];
            if(w + neighbor.second < dist[neighbor.first]){
                dist[neighbor.first] = w + neighbor.second;
                pq.push({dist[neighbor.first], neighbor.first});
            }
        }
    }
    int res = INF;
    for(int i = 1; i <= n; ++i){
        res = min(res, dist[i]);
    }
    cout << res;
    return 0;
}

import sys
import heapq

data = list(map(int, sys.stdin.read().strip().split()))
pos = 0

m, n = data[pos], data[pos + 1]
pos += 2

V = (m + 1) * n
graph = [[] for _ in range(V + 1)]
sz = 2 * m

for i in range(1, sz + 1):
    u = (i // 2) * n + 1
    if i % 2 != 0:
        for _ in range(n):
            w = data[pos]
            pos += 1
            v = u + n
            graph[u].append((v, w))
            graph[v].append((u, w))
            u += 1
    else:
        v = u + 1
        for _ in range(1, n):
            w = data[pos]
            pos += 1
            graph[u].append((v, w))
            graph[v].append((u, w))
            u += 1
            v += 1

INF = 10**9
dist = [INF] * (V + 1)
pq = [(0, V)]  # (cost, node)
dist[V] = 0

while pq:
    w, u = heapq.heappop(pq)
    if dist[u] != w:
        continue
    for v, cost in graph[u]:
        if w + cost < dist[v]:
            dist[v] = w + cost
            heapq.heappush(pq, (dist[v], v))

res = min(dist[1:n + 1])
print(res)

C++▶ Chạy tay từng dòng codeDựng đồ thị lưới (M + 1) × N từ input rồi chạy Dijkstra ngược từ phòng Bin Laden.

Dữ liệu vào (stdin) – sửa thoải mái4 2 99 10 1 10 99 1 99 10 1 10 99 1

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4#define int long long

5

6signed main(){

7 ios::sync_with_stdio(0);

8 cin.tie(0);

9 int m, n;

10 cin >> m >> n;

11 int V = (m + 1) * n;

12 vector<vector<pair<int, int>>> graph(V + 1, vector<pair<int, int>>());

13 int sz = 2 * m;

14 for(int i = 1; i <= sz; ++i){

15 int u = (i / 2) * n + 1;

16 int v, w;

17 if(i % 2 != 0){

18 for(int j = 1; j <= n; ++j){

19 cin >> w;

20 v = u + n;

21 graph[u].push_back({v, w});

22 graph[v].push_back({u, w});

23 u++;

24 }

25 }

26 else{

27 v = u + 1;

28 for(int j = 1; j < n; ++j){

29 cin >> w;

30 graph[u].push_back({v, w});

31 graph[v].push_back({u, w});

32 u++;

33 v++;

34 }

35 }

36 }

37

38 int INF = 1e9;

39 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // cost, u

40 vector<int> dist(V + 1, INF);

41 pq.push({0, V});

42 dist[V] = 0;

43 while(!pq.empty()){

44 pair<int, int> top = pq.top();

45 pq.pop();

46 int w = top.first;

47 int u = top.second;

48 if(dist[u] != w){

49 continue;

50 }

51 for(int i = 0; i < graph[u].size(); ++i){

52 pair<int, int> neighbor = graph[u][i];

53 if(w + neighbor.second < dist[neighbor.first]){

54 dist[neighbor.first] = w + neighbor.second;

55 pq.push({dist[neighbor.first], neighbor.first});

56 }

57 }

58 }

59 int res = INF;

60 for(int i = 1; i <= n; ++i){

61 res = min(res, dist[i]);

62 }

63 cout << res;

64 return 0;

65}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp

• Số đỉnh $V = (M + 1) \times N$ $\le 2223 \times 10$ $= 22230$, số cạnh $E \approx 2 \times M \times N \le 44440$.
• Độ phức tạp thời gian của Dijkstra dùng hàng đợi ưu tiên là $O((V + E) \log V)$, chỉ khoảng vài trăm nghìn phép tính nên chạy rất nhanh (mình chạy thử test lớn nhất $M = 2222$, $N = 10$ thì C++ mất khoảng 0.02 giây, Python khoảng 0.1 giây).
• Độ phức tạp không gian: $O(V + E)$ cho danh sách kề và mảng dist.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇