Tóm tắt đề bài

Cho một đồ thị gồm \(n\) đỉnh và \(m\) cạnh có trọng số. Có \(k\) địa điểm đặc biệt \(u_1, u_2, \dots, u_k\) mà tên tội phạm đã đi qua trên con đường ngắn nhất từ một điểm xuất phát \(x\) đến điểm kết thúc \(y\). Hãy tìm tất cả các đỉnh \(y\) có thể là nơi trú ẩn, sao cho tồn tại một đỉnh \(x\) và một đường đi ngắn nhất từ \(x\) đến \(y\) đi qua toàn bộ \(k\) đỉnh đặc biệt này.

Phân tích

• Điều kiện quan trọng: Đường đi từ \(x\) đến \(y\) phải là đường đi ngắn nhất và phải chứa tất cả \(k\) đỉnh đặc biệt.
• Nếu một đường đi ngắn nhất từ \(x\) đến \(y\) đi qua tập các đỉnh \(S = \{u_1, u_2, \dots, u_k\}\), thì tập \(S\) này phải nằm trên một "trục" đường đi ngắn nhất nào đó.

• Gọi \(d(u, v)\) là khoảng cách ngắn nhất giữa hai đỉnh \(u\) và \(v\). Một đỉnh \(v\) nằm trên đường đi ngắn nhất từ \(u\) đến \(w\) khi và chỉ khi:

  \[d(u, w) = d(u, v) + d(v, w)\]

• Với bài toán này, ta cần tìm các đỉnh \(y\) sao cho tồn tại \(x\) thỏa mãn \(k\) đỉnh đặc biệt nằm trên đường đi ngắn nhất \(x \to y\). Điều này tương đương với việc \(k\) đỉnh đặc biệt này phải có một thứ tự xuất hiện \(u_{p_1}, u_{p_2}, \dots, u_{p_k}\) sao cho:

  \[d(x, y) = d(x, u_{p_1}) + d(u_{p_1}, u_{p_2}) + \dots + d(u_{p_k}, y)\]

Hướng giải quyết

Nhận xét then chốt

Nếu tồn tại một cặp \((x, y)\) thỏa mãn yêu cầu, thì hai đỉnh "xa nhau nhất" trong tập \(k\) đỉnh đặc biệt (gọi là \(s\) và \(t\)) phải đóng vai trò là các mốc giới hạn. Cụ thể, mọi đỉnh đặc biệt khác phải nằm trên đường đi ngắn nhất giữa \(s\) và \(t\).

1. Tìm hai đỉnh \(s, t\) thuộc tập \(k\) đỉnh đặc biệt sao cho \(d(s, t)\) là lớn nhất trong mọi cặp đỉnh thuộc tập này. Cặp \((s, t)\) này có thể tìm được bằng cách:
   • Chọn một đỉnh đặc biệt bất kỳ, chạy Dijkstra để tìm đỉnh đặc biệt \(s\) xa nó nhất.
   • Từ \(s\), chạy Dijkstra để tìm đỉnh đặc biệt \(t\) xa \(s\) nhất.
2. Một đỉnh \(y\) là ứng cử viên nếu nó có thể "kéo dài" từ đường đi ngắn nhất chứa đủ \(k\) đỉnh. Có hai kịch bản:
   • \(y\) nằm trên hướng kéo dài từ \(s\) qua tập \(k\) đỉnh đến \(t\) rồi đến \(y\).
   • \(y\) nằm trên hướng kéo dài từ \(t\) qua tập \(k\) đỉnh đến \(s\) rồi đến \(y\).

Thuật toán chi tiết

1. Tìm hai cực của tập đặc biệt:
   • Chọn \(u_1\) trong tập đặc biệt. Chạy Dijkstra từ \(u_1\). Tìm \(s \in \{u_1, \dots, u_k\}\) có \(d(u_1, s)\) lớn nhất.
   • Chạy Dijkstra từ \(s\). Tìm \(t \in \{u_1, \dots, u_k\}\) có \(d(s, t)\) lớn nhất.
2. Kiểm tra tính hợp lệ của tập đặc biệt:
   • Tất cả \(k\) đỉnh đặc biệt phải nằm trên ít nhất một đường đi ngắn nhất giữa \(s\) và \(t\).
   • Điều này có nghĩa là với mọi \(u_i\), ta phải có \(d(s, t) = d(s, u_i) + d(u_i, t)\). Nếu không, tập đặc biệt không cùng nằm trên một đường đi ngắn nhất, kết quả là 0 (trừ trường hợp \(k=1\)).
3. Lan tỏa để tìm tập nghiệm \(y\):
   • Sử dụng hàm solve(root):
     • Chạy Dijkstra từ root (với root là \(s\) hoặc \(t\)).
     • Sắp xếp các đỉnh theo khoảng cách tăng dần từ root.
     • Sử dụng quy hoạch động/mảng đếm: specials[u] là số lượng đỉnh đặc biệt tối đa nằm trên đường đi ngắn nhất từ root đến \(u\).
     • Công thức truy hồi: Nếu \(d(root, v) = d(root, u) + w(u, v)\) thì specials[v] = max(specials[v], specials[u] + is_special[v]).
     • Nếu specials[u] == k, đỉnh \(u\) có thể là \(y\).
4. Kết hợp kết quả:
   • Một đỉnh \(y\) thỏa mãn nếu nó nhận đủ \(k\) đỉnh đặc biệt trên đường đi ngắn nhất từ \(s\) đến \(y\) HOẶC từ \(t\) đến \(y\).

Độ phức tạp

• Thời gian: \(O(M \log N)\) cho các lần chạy Dijkstra và \(O(N \log N)\) để sắp xếp các đỉnh.
• Bộ nhớ: \(O(N + M)\) để lưu trữ đồ thị và các mảng khoảng cách.

Code tham khảo

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

typedef long long ll;
typedef pair<ll, ll> pll;

const int MAXN = 200005;
const ll INF = 1e18;

int n, m, k;
vector<pair<int, int>> adj[MAXN];
int special_nodes[MAXN];
bool is_special[MAXN];
ll dist[MAXN];
int specials_count[MAXN];
bool can_be_y[MAXN];

void dijkstra(int start) {
    fill(dist, dist + n + 1, INF);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        ll d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

void solve(int start) {
    dijkstra(start);

    // Tạo danh sách các đỉnh và sắp xếp theo khoảng cách tăng dần
    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 1);
    sort(nodes.begin(), nodes.end(), [](int a, int b) {
        return dist[a] < dist[b];
    });

    fill(specials_count, specials_count + n + 1, 0);
    for (int u : nodes) {
        if (dist[u] == INF) continue;
        specials_count[u] += is_special[u];
        if (specials_count[u] == k) can_be_y[u] = true;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] == dist[u] + w) {
                specials_count[v] = max(specials_count[v], specials_count[u]);
            }
        }
    }
}

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

    cin >> n >> m >> k;
    vector<int> S;
    for (int i = 0; i < k; i++) {
        int u; cin >> u;
        S.push_back(u);
        is_special[u] = true;
    }

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    if (k == 1) {
        cout << n << "\n";
        for (int i = 1; i <= n; i++) cout << i << (i == n ? "" : " ");
        return 0;
    }

    // Tìm hai cực s và t của tập k đỉnh đặc biệt
    dijkstra(S[0]);
    int s = S[0];
    ll max_d = -1;
    for (int u : S) {
        if (dist[u] > max_d) {
            max_d = dist[u];
            s = u;
        }
    }

    dijkstra(s);
    int t = s;
    max_d = -1;
    for (int u : S) {
        if (dist[u] > max_d) {
            max_d = dist[u];
            t = u;
        }
    }

    // Chạy từ cả hai phía s và t
    solve(s);
    solve(t);

    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (can_be_y[i]) ans.push_back(i);
    }

    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}