Tóm tắt đề bài

Đề bài: Đường đi ngắn nhất chứa toàn bộ đỉnh đặc biệt

• Mô tả:
  Cho một đồ thị vô hướng có trọng số với ~ n ~ đỉnh và ~ m ~ cạnh. Ngoài ra, ta có một tập hợp gồm ~ k ~ đỉnh đặc biệt (được đánh số từ 1 đến ~ n ~).
  Một đường đi hợp lệ được định nghĩa là một đường đi ngắn nhất giữa hai đỉnh của đồ thị sao cho trên đường đi đó có chứa tất cả các đỉnh đặc biệt (theo thứ tự xuất hiện không cần liên tục, nhưng không bỏ sót bất kỳ đỉnh đặc biệt nào).

• Nhiệm vụ:
  Tìm và in ra danh sách các đỉnh của đồ thị mà tồn tại ít nhất một đường đi ngắn nhất hợp lệ (tức là chứa đầy đủ các đỉnh đặc biệt) đi qua chúng.

• Đầu vào:

  1. Dòng đầu tiên gồm ba số nguyên: ~ n ~, ~ m ~ và ~ k ~ – tương ứng với số đỉnh, số cạnh và số đỉnh đặc biệt.
  2. Dòng thứ hai gồm ~ k ~ số nguyên: chỉ số của các đỉnh đặc biệt (được đánh số từ 1 đến ~ n ~).
  3. Tiếp theo là ~ m ~ dòng, mỗi dòng gồm ba số nguyên ~ a ~, ~ b ~ và ~ c ~ mô tả một cạnh nối đỉnh ~ a ~ và đỉnh ~ b ~ với trọng số ~ c ~.

• Đầu ra:

  1. Dòng đầu tiên in ra số lượng các đỉnh thoả mãn yêu cầu.
  2. Dòng thứ hai in ra danh sách các đỉnh thoả mãn (theo hệ 1-indexed, thứ tự in theo thứ tự tăng dần).

Tóm tắt ý tưởng giải bài toán:

Để xác định các đỉnh nằm trên ít nhất một đường đi ngắn nhất chứa tất cả các đỉnh đặc biệt, ta thực hiện các bước chính sau:

1. Đọc dữ liệu, kiểm tra tính liên thông của đồ thị
2. Xử lý trường hợp ~ k = 1 ~:
   Nếu chỉ có 1 đỉnh đặc biệt, in ra tất cả các đỉnh của đồ thị.
3. Xác định hai đầu của đường đi đặc biệt:
   
   • Chọn một đỉnh đặc biệt ban đầu, sau đó chạy thuật toán Dijkstra để tìm đỉnh đặc biệt cách đỉnh đó xa nhất (gọi là ~ \texttt{start1} ~).
   • Dựa vào khoảng cách từ ~ \texttt{start1} ~, chọn đỉnh đặc biệt cách xa nhất (gọi là ~ \texttt{start2} ~).
     Hai đỉnh ~ \texttt{start1} ~ và ~ \texttt{start2} ~ được xem như hai cực biên của tập đỉnh đặc biệt.
4. Quy hoạch động trên đường đi ngắn nhất:
   
   • Từ mỗi trong số ~ \texttt{start1} ~ và ~ \texttt{start2} ~, chạy Dijkstra để tính khoảng cách ngắn nhất đến tất cả các đỉnh.
   • Sắp xếp các đỉnh theo thứ tự khoảng cách tăng dần và sử dụng phương pháp quy hoạch động để truyền đạt số lượng đỉnh đặc biệt đã gặp được trên các đường đi ngắn nhất đó.
   • Một đỉnh được đánh dấu thoả mãn nếu từ nguồn ~ \texttt{start1} ~ hoặc ~ \texttt{start2} ~ có một đường đi ngắn nhất qua đỉnh đó chứa đủ ~ k ~ đỉnh đặc biệt.
5. Kết hợp kết quả:
   In ra các đỉnh mà trên ít nhất một đường đi ngắn nhất từ ~ \texttt{start1} ~ hoặc ~ \texttt{start2} ~ thu thập được đủ các đỉnh đặc biệt.

Phân tích cụ thể thuật toán

1. Xây dựng đồ thị và đọc dữ liệu

• Đầu vào:
  Chương trình đọc vào số đỉnh n, số cạnh m và số đỉnh đặc biệt k.
  Sau đó, nó đọc danh sách các đỉnh đặc biệt (được lưu vào vector special và được đánh dấu trong mảng is_special[]) và danh sách các cạnh.

• Cấu trúc lưu trữ đồ thị:

  • C: vector các vector lưu danh sách kề của mỗi đỉnh.
  • CW: vector các vector lưu trọng số của các cạnh ứng với danh sách kề tại C.
  • ind: vector chứa các chỉ số của các đỉnh (0 đến n–1), dùng để sắp xếp theo khoảng cách trong quá trình xử lý sau này.

• Kiểm tra liên thông:
  Hàm connected() dùng BFS (Breadth-First Search) từ đỉnh 0 để đảm bảo rằng đồ thị là liên thông (số đỉnh được thăm phải bằng n).

2. Xử lý trường hợp đặc biệt: k = 1

• Nếu chỉ có một đỉnh đặc biệt, ta nhận thấy rằng với bất kỳ đường đi ngắn nhất nào bắt đầu từ đỉnh đặc biệt đó, luôn có chứa đỉnh đặc biệt ban đầu.
• Vì vậy, chương trình sẽ in tất cả các đỉnh của đồ thị làm kết quả.

3. Xác định hai đầu của tập đỉnh đặc biệt

Ý tưởng quan trọng ở đây là:

Mọi đường đi ngắn nhất chứa tất cả các đỉnh đặc biệt phải qua hai đỉnh đặc biệt cực biên (các đỉnh cách xa nhau nhất trong tập đặc biệt).

Quá trình thực hiện như sau:

1. Chọn start1:

   • Chạy thuật toán Dijkstra từ đỉnh đặc biệt đầu tiên (special[0]).
   • Sau đó, duyệt qua các đỉnh đặc biệt và chọn đỉnh có khoảng cách từ special[0] lớn nhất làm start1.

2. Chọn start2:

   • Gọi hàm solve(start1) (chi tiết ở phần dưới) để xử lý từ start1.
   • Sau đó, với vector ind đã được sắp xếp theo khoảng cách từ start1, duyệt qua và chọn đỉnh đặc biệt cuối cùng (tức đỉnh có khoảng cách từ start1 lớn nhất trong tập đặc biệt) làm start2.

Như vậy, start1 và start2 được xem như hai đầu của đường kính của tập các đỉnh đặc biệt.

4. Thuật toán Dijkstra (Hàm dijkstra(start))

• Mục đích:
  Tính khoảng cách ngắn nhất từ đỉnh nguồn start đến tất cả các đỉnh còn lại.

• Cách làm:

  • Sử dụng một priority queue để chọn đỉnh có khoảng cách tạm thời nhỏ nhất.
  • Mảng DIST[] lưu khoảng cách từ start đến các đỉnh.
  • Một mảng phụ upd[] kết hợp với biến counter được dùng để đánh dấu một đỉnh đã xử lý trong phiên chạy hiện tại (tránh việc xử lý lại cùng một đỉnh nhiều lần).

• Chú ý:
  Priority queue được sử dụng với các giá trị âm của khoảng cách (tương đương với việc sử dụng min-heap) vì C++ priority_queue mặc định là max-heap.

5. Quy hoạch động theo thứ tự khoảng cách (Hàm solve(start))

Mục tiêu của hàm này là xác định các đỉnh nằm trên một số đường đi ngắn nhất từ start mà thu thập được tất cả các đỉnh đặc biệt.

Quy trình thực hiện:

1. Chạy Dijkstra:
   Gọi dijkstra(start) để tính khoảng cách từ start đến tất cả các đỉnh (mảng DIST[]).

2. Sắp xếp các đỉnh:
   Sắp xếp vector ind theo thứ tự tăng dần của DIST[] (điều này đảm bảo rằng khi xử lý một đỉnh, ta đã xử lý xong các đỉnh có khoảng cách nhỏ hơn).

3. Quy hoạch động (Dynamic Programming):

   • Sử dụng mảng specials[], trong đó specials[v] lưu số đỉnh đặc biệt tối đa có thể thu thập được trên một đường đi ngắn nhất từ start đến đỉnh v.
   • Với mỗi đỉnh a theo thứ tự đã sắp xếp:
     • Bước 1: Cập nhật specials[a] bằng cách cộng thêm giá trị is_special[a] (nếu a là đỉnh đặc biệt, thêm 1; nếu không thì không thay đổi).
     • Bước 2: Nếu sau cập nhật, specials[a] bằng k (tức là đường đi đến a đã thu thập đủ tất cả các đỉnh đặc biệt), thì đánh dấu ANS[a] = 1.
     • Bước 3: Với mỗi cạnh xuất phát từ a đến các đỉnh kề j có trọng số w, nếu điều kiện chặt chẽ của đường đi ngắn nhất thỏa mãn (tức là DIST[j] == DIST[a] + w), thì cập nhật: ~ specials[j] = \max(specials[j], specials[a]) ~ Điều này có nghĩa là từ start đến j có thể mượn được số lượng đỉnh đặc biệt tối đa thu thập được đến a.

• Ý nghĩa của specials[]:
  Ở mỗi đỉnh, giá trị này đại diện cho số lượng đỉnh đặc biệt có thể có trên một đường đi ngắn nhất từ start đến đỉnh đó, theo cách tối ưu (lấy giá trị lớn nhất khi có nhiều khả năng đến từ các đường đi khác nhau).

6. Kết hợp kết quả từ hai lần chạy solve

Sau khi đã tìm được hai đỉnh cực biên start1 và start2:

• Chạy solve(start1):
  Đánh dấu các đỉnh mà trên một đường đi ngắn nhất từ start1 có thể thu thập đủ k đỉnh đặc biệt.

• Chọn start2 và chạy solve(start2):
  Tương tự, đánh dấu thêm các đỉnh mà trên một đường đi ngắn nhất từ start2 có đủ các đỉnh đặc biệt.

• Lưu ý:
  Vì bất kỳ đường đi ngắn nhất nào chứa tất cả các đỉnh đặc biệt nhất định phải đi qua cả hai đầu của đường kính (theo nhận xét trên đường kính của tập đặc biệt), nên việc xét từ cả start1 và start2 sẽ bao phủ được toàn bộ các đỉnh nằm trên ít nhất một đường đi ngắn nhất có chứa tất cả các đỉnh đặc biệt.

7. In kết quả

• Sau khi kết hợp kết quả từ các lần chạy solve, chương trình đếm số đỉnh có ANS[v] = 1 và in ra:
  • Số lượng các đỉnh thoả mãn.
  • Danh sách các đỉnh đó (sau chuyển về chỉ số 1-indexed).

Chương trình minh hoạ

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pli; // (khoảng cách, đỉnh)

const int MAXN = 200000;

// Biến toàn cục
int n, m, k; // n: số đỉnh, m: số cạnh, k: số đỉnh đặc biệt
vector<vector<int>> adj(MAXN);          // Danh sách kề của đồ thị (lưu chỉ số các đỉnh)
vector<vector<ll>> adjWeight(MAXN);       // Trọng số tương ứng với các cạnh trong adj
vector<int> specialVertices;              // Danh sách các đỉnh đặc biệt (lưu theo chỉ số 0-index)
bool isSpecial[MAXN] = { false };         // isSpecial[u] = true nếu u là đỉnh đặc biệt
vector<int> ind;                          // Mảng chứa các chỉ số đỉnh từ 0 đến n-1

ll dist[MAXN];        // Lưu khoảng cách từ nguồn (trong hàm Dijkstra)
ll upd[MAXN] = { 0 }; // Mảng dùng để đánh dấu xem đỉnh đã được xử lý trong phiên chạy Dijkstra hiện tại
ll dijkstraRunCounter = 0; // Biến đếm phiên chạy Dijkstra

// Hàm kiểm tra đồ thị liên thông (sử dụng BFS)
bool connected() {
    vector<bool> visited(n, false);
    int cnt = 0;
    queue<int> q;
    q.push(0);
    visited[0] = true;
    cnt++;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                cnt++;
                q.push(v);
            }
        }
    }
    return (cnt == n);
}

// Thuật toán Dijkstra: Tính khoảng cách ngắn nhất từ đỉnh 'start' đến tất cả các đỉnh
void dijkstra(int start) {
    dijkstraRunCounter++; // Tăng bộ đếm phiên chạy
    // Khởi tạo khoảng cách của tất cả các đỉnh là -1 (nghĩa là chưa thăm)
    for (int i = 0; i < n; i++) {
        dist[i] = -1;
    }
    // Sử dụng priority_queue với khoảng cách âm để mô phỏng min-heap
    priority_queue<pli> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (upd[u] != dijkstraRunCounter) {
            upd[u] = dijkstraRunCounter;
            for (size_t i = 0; i < adj[u].size(); i++) {
                int v = adj[u][i];
                ll w = adjWeight[u][i];
                if (dist[v] == -1 || dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.push({ -dist[v], v });
                }
            }
        }
    }
}

// Hàm so sánh dùng cho sort: sắp xếp các đỉnh theo khoảng cách từ nguồn (tăng dần)
bool comp(int u, int v) {
    return dist[u] < dist[v];
}

bool answer[MAXN] = { false };       // answer[u] = true nếu u nằm trên một đường đi ngắn nhất có chứa đủ k đỉnh đặc biệt
ll specialsCount[MAXN] = { 0 };        // specialsCount[u]: số đỉnh đặc biệt có thể thu thập được dọc theo đường đi ngắn nhất từ nguồn tới u

// Hàm solve: Từ một đỉnh nguồn start, tính đường đi ngắn nhất và sử dụng quy hoạch động để truyền đạt số đỉnh đặc biệt có thể thu thập
void solve(int start) {
    dijkstra(start);
    // Sắp xếp lại mảng các đỉnh theo khoảng cách từ start
    sort(ind.begin(), ind.end(), comp);
    // Khởi tạo lại mảng specialsCount
    for (int i = 0; i < n; i++) {
        specialsCount[i] = 0;
    }
    // Duyệt các đỉnh theo thứ tự tăng dần của khoảng cách
    for (int idx = 0; idx < n; idx++) {
        int u = ind[idx];
        // Nếu u là đỉnh đặc biệt, cộng thêm 1
        if (isSpecial[u])
            specialsCount[u]++;
        // Nếu tại u, số đỉnh đặc biệt thu thập được đủ k, đánh dấu u là đáp án
        if (specialsCount[u] == k)
            answer[u] = true;
        // Cập nhật cho các đỉnh kề của u nếu chúng thuộc đường đi ngắn nhất từ start
        for (size_t j = 0; j < adj[u].size(); j++) {
            int v = adj[u][j];
            ll w = adjWeight[u][j];
            if (dist[v] == dist[u] + w)
                specialsCount[v] = max(specialsCount[v], specialsCount[u]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Đọc dữ liệu đầu vào
    cin >> n >> m >> k;

    // Đọc danh sách các đỉnh đặc biệt (input dạng 1-indexed, chuyển về 0-indexed)
    for (int i = 0; i < k; i++) {
        int v;
        cin >> v;
        v--; // chuyển về 0-indexed
        specialVertices.push_back(v);
        isSpecial[v] = true;
    }

    // Khởi tạo mảng ind với các đỉnh từ 0 đến n-1
    for (int i = 0; i < n; i++) {
        ind.push_back(i);
    }

    // Đọc danh sách các cạnh (đồ thị vô hướng)
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--; v--; // chuyển về 0-indexed
        adj[u].push_back(v);
        adj[v].push_back(u);
        adjWeight[u].push_back(w);
        adjWeight[v].push_back(w);
    }

    // Kiểm tra tính liên thông của đồ thị
    assert(connected());

    // Trường hợp đặc biệt: nếu chỉ có 1 đỉnh đặc biệt thì mọi đỉnh đều thỏa mãn
    if (k == 1) {
        cout << n << endl;
        for (int i = 0; i < n; i++) {
            cout << i + 1 << ' ';
        }
        cout << endl;
        return 0;
    }

    // Xác định đỉnh đặc biệt start1:
    // Chạy Dijkstra từ specialVertices[0] và chọn đỉnh đặc biệt cách xa nhất từ specialVertices[0]
    dijkstra(specialVertices[0]);
    int start1 = specialVertices[0];
    ll maxDistance = 0;
    for (int v : specialVertices) {
        if (dist[v] > maxDistance) {
            maxDistance = dist[v];
            start1 = v;
        }
    }

    // Chạy hàm solve từ start1
    solve(start1);

    // Xác định đỉnh start2:
    // Duyệt mảng ind đã sắp xếp theo khoảng cách từ start1 và chọn đỉnh đặc biệt cuối cùng (cách xa nhất)
    int start2 = start1;
    for (int idx = 0; idx < n; idx++) {
        if (isSpecial[ind[idx]])
            start2 = ind[idx];
    }
    // Chạy hàm solve từ start2
    solve(start2);

    // Đếm số đỉnh thoả mãn và in ra kết quả
    int countAnswer = 0;
    for (int i = 0; i < n; i++) {
        if (answer[i])
            countAnswer++;
    }
    cout << countAnswer << endl;

    bool firstOutput = true;
    for (int i = 0; i < n; i++) {
        if (answer[i]) {
            if (!firstOutput)
                cout << ' ';
            cout << i + 1; // chuyển về 1-indexed khi in ra
            firstOutput = false;
        }
    }
    cout << endl;

    return 0;
}