Tóm tắt đề bài

Cho một đồ thị vô hướng gồm \(N\) đỉnh và \(M\) cạnh có trọng số. Tìm độ dài của đường đi ngắn thứ hai nghiêm ngặt từ đỉnh \(1\) đến đỉnh \(N\). Đường đi ngắn thứ hai nghiêm ngặt là đường đi có độ dài nhỏ nhất trong tất cả các đường đi có độ dài lớn hơn độ dài đường đi ngắn nhất.

Lưu ý: Một đường đi có thể đi qua một đỉnh hoặc một cạnh nhiều lần.

Phân tích

• Điều kiện: \(N, M \le 2 \cdot 10^5\), trọng số cạnh \(w \le 5000\).
• Đường đi ngắn thứ hai nghiêm ngặt: Nếu đường đi ngắn nhất có độ dài là \(L\), ta cần tìm đường đi có độ dài \(L'\) sao cho \(L' > L\) và \(L'\) là nhỏ nhất có thể.
• Tính chất: Trong thuật toán Dijkstra thông thường, ta chỉ quan tâm đến khoảng cách ngắn nhất đến mỗi đỉnh. Để tìm đường đi ngắn thứ hai, tại mỗi đỉnh \(u\), ta cần lưu trữ hai giá trị:
  1. \(dist1[u]\): Khoảng cách ngắn nhất từ nguồn đến \(u\).
  2. \(dist2[u]\): Khoảng cách ngắn thứ hai nghiêm ngặt từ nguồn đến \(u\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) hoặc quay lui để liệt kê mọi đường đi có thể từ \(1\) đến \(N\). Tuy nhiên, vì đồ thị có thể có chu trình và đề bài cho phép đi qua một cạnh nhiều lần, số lượng đường đi có thể là vô hạn. Một cách tiếp cận "trâu" hơn là sử dụng Dijkstra nhưng cho phép mỗi đỉnh được thăm nhiều lần (không chỉ 2 lần), nhưng điều này vẫn không hiệu quả và khó kiểm soát.

Với Subtask 1 (\(N, M \le 500\)), ta có thể thử xóa từng cạnh của đường đi ngắn nhất rồi tìm đường đi ngắn nhất trên đồ thị mới, nhưng cách này không bao quát được trường hợp đường đi ngắn thứ hai sử dụng lại toàn bộ các cạnh của đường đi ngắn nhất (ví dụ đi vòng qua một cạnh rồi quay lại).

Độ phức tạp

• Thời gian: Rất lớn (tùy thuộc vào cách giới hạn số bước).
• Đánh giá: Không khả thi cho các ràng buộc lớn.

Hướng giải quyết (Tối ưu)

Nhận xét

Thuật toán Dijkstra có thể được mở rộng để tìm \(k\) khoảng cách ngắn nhất. Với bài toán này (\(k=2\)), ta cải tiến điều kiện cập nhật khoảng cách như sau:

Khi xét cạnh \((u, v)\) có trọng số \(w\), giả sử ta có một đường đi mới đến \(v\) thông qua \(u\) với độ dài \(nd = dist + w\):

1. Nếu \(nd < dist1[v]\):
   • Khoảng cách ngắn nhất cũ của \(v\) trở thành khoảng cách ngắn thứ hai: \(dist2[v] = dist1[v]\).
   • Cập nhật khoảng cách ngắn nhất mới: \(dist1[v] = nd\).
   • Đẩy cả hai trạng thái vào hàng đợi ưu tiên (priority queue).
2. Nếu \(nd > dist1[v]\) và \(nd < dist2[v]\):
   • Cập nhật khoảng cách ngắn thứ hai: \(dist2[v] = nd\).
   • Đẩy trạng thái này vào hàng đợi ưu tiên.
3. Các trường hợp khác (\(nd = dist1[v]\) hoặc \(nd \ge dist2[v]\)): Bỏ qua vì không tạo ra đường đi ngắn thứ hai nghiêm ngặt.

Các bước thực hiện

1. Khởi tạo \(dist1[i] = dist2[i] = \infty\) với mọi \(i\), ngoại trừ \(dist1[1] = 0\).
2. Sử dụng priority_queue lưu cặp \((distance, u)\) để thực hiện Dijkstra.
3. Mỗi khi lấy một đỉnh \(u\) ra khỏi hàng đợi, duyệt các đỉnh \(v\) kề với nó và cập nhật \(dist1[v], dist2[v]\) theo quy tắc trên.
4. Kết quả cuối cùng là \(dist2[N]\).

Độ phức tạp

• Thời gian: \(O(M \log N)\), tương tự như thuật toán Dijkstra thông thường nhưng mỗi đỉnh có thể được đẩy vào hàng đợi tối đa 2 lần.
• Bộ nhớ: \(O(N + M)\) để lưu đồ thị và mảng khoảng cách.

Code tham khảo

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

const long long INF = 1e18;

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

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> adj(n + 1);
    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});
    }

    // dist1: ngắn nhất, dist2: ngắn thứ hai nghiêm ngặt
    vector<long long> dist1(n + 1, INF);
    vector<long long> dist2(n + 1, INF);

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dist1[1] = 0;
    pq.push({0, 1});

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

        // Nếu khoảng cách lấy ra lớn hơn dist2 hiện tại thì không thể tối ưu thêm
        if (d > dist2[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            long long nd = d + w;

            if (nd < dist1[v]) {
                // Đường đi mới ngắn hơn cả dist1, đẩy dist1 xuống dist2
                dist2[v] = dist1[v];
                dist1[v] = nd;
                pq.push({dist1[v], v});
                pq.push({dist2[v], v});
            } else if (nd > dist1[v] && nd < dist2[v]) {
                // Đường đi mới nằm giữa dist1 và dist2
                dist2[v] = nd;
                pq.push({dist2[v], v});
            }
        }
    }

    if (dist2[n] == INF) cout << -1;
    else cout << dist2[n];

    return 0;
}

import heapq
import sys

def solve():
    input = sys.stdin.read().split()
    if not input:
        return

    n = int(input[0])
    m = int(input[1])

    adj = [[] for _ in range(n + 1)]
    idx = 2
    for _ in range(m):
        u = int(input[idx])
        v = int(input[idx+1])
        w = int(input[idx+2])
        adj[u].append((v, w))
        adj[v].append((u, w))
        idx += 3

    inf = float('inf')
    dist1 = [inf] * (n + 1)
    dist2 = [inf] * (n + 1)

    dist1[1] = 0
    pq = [(0, 1)]

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist2[u]:
            continue

        for v, w in adj[u]:
            nd = d + w

            if nd < dist1[v]:
                dist2[v] = dist1[v]
                dist1[v] = nd
                heapq.heappush(pq, (dist1[v], v))
                heapq.heappush(pq, (dist2[v], v))
            elif dist1[v] < nd < dist2[v]:
                dist2[v] = nd
                heapq.heappush(pq, (dist2[v], v))

    if dist2[n] == inf:
        print("-1")
    else:
        print(dist2[n])

if __name__ == "__main__":
    solve()