28.2 Dijkstra ด้วย priority_queue

Dijkstra แบบอาเรย์เสียเวลาเกือบทั้งหมดไปกับการไล่หาจุดที่ใกล้ที่สุด รอบละ V ช่อง โจทย์ค่าย 2 และ TOI ส่วนใหญ่ให้ V ถึงแสน และ E ถึงสองแสน ซึ่ง V² คือ 10¹⁰ ไม่ทันแน่นอน งาน "ใส่ค่าเข้าไปเรื่อยๆ แล้วหยิบค่าน้อยที่สุดออก" คืองานของ priority_queue ในหน้า 20.5 พอดี หน้านี้เปลี่ยนการไล่หาเป็น priority_queue ซึ่งเป็นแบบที่ใช้จริงในการแข่งขัน แล้วดูกับดักสามข้อที่ทำให้คนเสียคะแนนบ่อยที่สุด

เก็บคู่ (ระยะ, จุด) ไว้ในคิว

ใส่คู่ (dist[v], v) ลงใน priority_queue แบบน้อยสุดก่อน ทุกครั้งที่หยิบออก จะได้จุดที่ระยะน้อยที่สุดในเวลา log ของขนาดคิว แทนการไล่ V ช่อง ปัญหาคือเมื่อผ่อนแล้ว dist[v] ลดลง ค่าของ v ที่อยู่ในคิวอยู่แล้วต้องเปลี่ยนตาม แต่ priority_queue แก้ค่าของที่อยู่ข้างในไม่ได้ ทำได้แค่ใส่กับหยิบ

ทางออกคือ ไม่ต้องแก้ ใส่คู่ใหม่ (ระยะใหม่, v) ลงไปอีกตัว ปล่อยคู่เก่าค้างไว้ในคิว คู่ใหม่ระยะน้อยกว่าจึงออกมาก่อนเสมอ พอคู่เก่าออกมาทีหลัง ก็ดูออกได้ทันทีว่ามันเก่า เพราะระยะในคู่มากกว่า dist[v] ปัจจุบัน ให้ข้ามไปเฉยๆ วิธีปล่อยของเก่าค้างแล้วค่อยทิ้งตอนหยิบออกมาแบบนี้เรียกว่า lazy deletion

#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});
    }
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; // (1)!
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) { // (2)!
            cout << "skip " << u << " d=" << d << '\n';
            continue;
        }
        cout << "take " << u << " dist=" << d << '\n';
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v}); // (3)!
            }
        }
    }
    for (int u = 1; u <= n; u++) {
        cout << (dist[u] == INF ? -1 : dist[u]) << (u == n ? '\n' : ' ');
    }
    return 0;
}

priority_queue แบบน้อยสุดก่อนตามหน้า 20.5 เก็บ pair ช่องแรกคือระยะ จึงเรียงตามระยะ ระยะเป็น long long ช่องแรกของ pair จึงต้องเป็น long long ด้วย
คู่นี้เก่าแล้ว เคยมีคู่ที่ระยะน้อยกว่าของจุดเดียวกันออกไปก่อน ข้ามไปเลย โปรแกรมจริงไม่ต้องพิมพ์ ตัวอย่างนี้พิมพ์ไว้ให้เห็น
ทุกครั้งที่ระยะลดลงให้ใส่คู่ใหม่ จุดเดียวกันจึงอยู่ในคิวได้หลายคู่

take 1 dist=0
take 3 dist=1
take 2 dist=3
skip 2 d=4
take 4 dist=8
skip 4 d=9
take 5 dist=10
skip 5 d=11
take 6 dist=13
skip 6 d=14
0 3 1 8 10 13

ลำดับ take ตรงกับแบบอาเรย์ในหน้า 28.1 ทุกบรรทัด บรรทัด skip คือคู่เก่าที่ค้างอยู่ เช่น ตลาดเคยถูกใส่เป็น (4, 2) ตอนผ่อนจากบ้าน แล้วถูกใส่อีกครั้งเป็น (3, 2) ตอนผ่อนจากวัด คู่ (3, 2) ออกก่อนและถูกใช้ คู่ (4, 2) ออกทีหลังจึงถูกข้าม

ใน for ที่ผ่อนถนน ใช้ d + w ไม่ใช่ dist[u] + w สองค่านี้เท่ากันเสมอหลังผ่านบรรทัดที่ข้ามคู่เก่าแล้ว เขียนแบบไหนก็ได้ แต่หน้า 28.3 จะแสดงว่าถ้าลืมบรรทัดที่ข้าม สองแบบนี้ให้ผลต่างกัน

ความซับซ้อน

นับว่าแต่ละอย่างเกิดขึ้นกี่ครั้ง

คู่ใหม่ถูกใส่ทุกครั้งที่ผ่อนสำเร็จ ผ่อนได้ไม่เกินจำนวนครั้งที่ดูถนน คือราว 2E ครั้งเมื่อถนนเป็นสองทาง คิวจึงมีของไม่เกินราว 2E ตัว ใส่และหยิบตัวละ O(log E)
แต่ละจุดผ่านบรรทัดที่ข้ามไปได้ครั้งเดียว จึงดูถนนของตัวเองครั้งเดียว รวม O(V + E)
E ไม่เกิน V² ทำให้ log E ไม่เกิน 2 log V จึงเขียนเป็น log V ได้

รวมเป็น O((V + E) log V) ที่ V เป็นแสนและ E เป็นสองแสน ได้ราว 3 × 10⁵ × 17 ประมาณห้าล้านขั้น สบายมาก

เร็วขึ้นแค่ไหน

วัดบนเครื่องเดียวกับหน้า 28.1 คอมไพล์แบบ -O2 กราฟสุ่มด้วย mt19937 น้ำหนัก 1 ถึง 10⁹ ทุกจุดไปถึงกันได้ จับเวลาเฉพาะช่วง Dijkstra แต่ละช่องเป็นค่ากลางของ 5 รอบ

กราฟ	แบบอาเรย์ O(V² + E)	แบบ priority_queue O((V + E) log V)
V = 10⁴, E = 2 × 10⁴	0.128 วินาที	0.002 วินาที
V = 10⁵, E = 2 × 10⁵	20.875 วินาที (วัด 3 รอบ)	0.029 วินาที
V = 3000 ทุกคู่มีถนน น้ำหนักสุ่ม	0.017 วินาที	0.010 วินาที
V = 3000 ทุกคู่มีถนน น้ำหนักแบบที่ผ่อนสำเร็จเกือบทุกครั้ง	0.018 วินาที	0.878 วินาที

กราฟที่เส้นน้อย (sparse) แบบที่โจทย์ส่วนใหญ่ให้ แบบ priority_queue เร็วกว่าหลายสิบเท่าที่ V เป็นหมื่น และหลายร้อยเท่าที่ V เป็นแสน ซึ่งแบบอาเรย์ใช้กว่ายี่สิบวินาที แต่สองแถวล่างคือกราฟที่ทุกคู่มีถนน (dense) E ราวสี่ล้านครึ่ง น้ำหนักสุ่มยังสูสีกัน เพราะถนนส่วนใหญ่ผ่อนไม่สำเร็จ คิวจึงไม่ค่อยโต แถวสุดท้ายใช้น้ำหนัก 2|u - v| - 1 ซึ่งทำให้ทุกครั้งที่เลือกจุดใหม่ ระยะของทุกจุดที่เหลือลดลง คิวจึงต้องรับของหลายล้านตัว แบบ priority_queue กลายเป็น O(V² log V) และช้ากว่าแบบอาเรย์ราวห้าสิบเท่า

เลือกแบบไหน

โจทย์ที่ E ใกล้ V² เช่นให้ระยะของทุกคู่มาเป็นตาราง V × V และ V ไม่เกินหลักพัน แบบอาเรย์ทั้งง่ายกว่าและไม่มีทางช้ากว่า V² นอกนั้นใช้แบบ priority_queue หน้า 28.5 มีตารางเลือกวิธีครบทุกแบบ

ลองทำให้พัง

แบบที่ 1 ไม่ข้ามคู่เก่า

บรรทัด if (d > dist[u]) continue; ดูเหมือนไม่จำเป็น เพราะถ้าลบทิ้ง คู่เก่าที่ออกมาจะผ่อนถนนด้วยระยะที่มากกว่าเดิม ซึ่งไม่มีทางทำให้อะไรดีขึ้น คำตอบจึงยังถูก แต่ทุกครั้งที่คู่เก่าออกมา มันไล่ดูถนน ทุกเส้น ของจุดนั้นซ้ำ ถ้าจุดที่มีถนนเยอะถูกใส่ลงคิวหลายครั้ง งานจะระเบิด

โปรแกรมนี้สร้างกราฟที่ตั้งใจให้เกิดแบบนั้น add คือ lambda แบบหน้า 16.3 แต่แทนที่จะส่งให้ sort เราเก็บมันไว้ในตัวแปรชื่อ add ชนิดของ lambda ไม่มีชื่อให้เขียน จึงประกาศด้วย auto จากหน้า 15.5 จากนั้นเรียก add(1, 2, 5) ได้เหมือนฟังก์ชันธรรมดา ส่วน [&] ทำให้ข้างใน lambda ใช้ตัวแปร adj ของ main ได้ และแก้ที่ตัวจริง ไม่ใช่สำเนา ถ้าเขียนเป็นฟังก์ชันธรรมดานอก main ต้องส่ง adj เข้าไปด้วยทุกครั้ง จุด 1 มีถนนไปจุดป้อน k จุด ทุกจุดป้อนมีถนนไปจุดศูนย์กลางจุดเดียว น้ำหนักตั้งไว้ให้ทุกครั้งที่จุดป้อนถูกเลือก ระยะของศูนย์กลางลดลง ศูนย์กลางจึงถูกใส่ลงคิว k ครั้ง และศูนย์กลางมีถนนไปจุดปลายอีก L จุด ตัวแปร skip_old เลือกว่าจะข้ามคู่เก่าหรือไม่ โปรแกรมนับด้วยว่าดูถนนไปกี่ครั้ง

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

const long long INF = 1e18;

int main()
{
    int feeders, leaves, skip_old;
    cin >> feeders >> leaves >> skip_old;
    int n = feeders + leaves + 2;
    int hub = feeders + 2;
    vector<vector<pair<int, int>>> adj(n + 1);
    auto add = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    };
    for (int i = 1; i <= feeders; i++) {
        add(1, 1 + i, i);
        add(1 + i, hub, 3 * feeders - 2 * i);
    }
    for (int j = 1; j <= leaves; j++) {
        add(hub, hub + j, 1);
    }
    clock_t start = clock();
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    long long scanned = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (skip_old && d > dist[u]) {
            continue;
        }
        for (auto [v, w] : adj[u]) {
            scanned++;
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    clock_t end = clock();
    long long total = 0;
    for (int u = 1; u <= n; u++) {
        total += dist[u];
    }
    cout << "n = " << n << " edges scanned = " << scanned << " sum = " << total << '\n';
    cout << "time = " << fixed << setprecision(3) << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}

ข้อมูลเข้า	ดูถนน	เวลา `-O2` (ค่ากลาง 5 รอบ)
`50000 50000 1` ข้ามคู่เก่า	300000 ครั้ง	0.009 วินาที
`50000 50000 0` ไม่ข้าม	5000200000 ครั้ง	2.777 วินาที

กราฟมีแค่ 100002 จุดกับ 150000 เส้น แต่แบบไม่ข้ามดูถนนห้าพันล้านครั้ง เพราะคู่เก่าของศูนย์กลางห้าหมื่นคู่ แต่ละคู่ไล่ถนนของศูนย์กลางแสนเส้นซ้ำ ผลรวมระยะที่พิมพ์ออกมาเท่ากันทั้งสองแบบ ชุดทดสอบที่ตัวเลขเล็กจึงจับไม่ได้ แต่ชุดที่ออกแบบมาดักแบบนี้จะเกินเวลา บรรทัดที่ข้ามคู่เก่าจึงต้องมีทุกครั้ง

แบบที่ 2 ลืม greater

ประกาศคิวเป็น priority_queue<pair<long long, int>> pq; เพราะลืมว่าค่าเริ่มต้นคือมากสุดก่อน ตามที่หน้า 20.5 เตือนไว้ ผลแปลกกว่าที่คิด คือกับแผนที่เมืองยัง ได้คำตอบถูก 0 3 1 8 10 13 แต่ take ออกมา 11 ครั้งแทน 6 ครั้ง เพราะหยิบจุดที่ไกลที่สุดก่อน แล้วระยะของมันลดลงทีหลังจึงต้องทำซ้ำ บรรทัดที่ข้ามคู่เก่ากันไม่ให้ผิด แต่กันไม่ให้ทำซ้ำไม่ได้ วัดบนเครื่องเดียวกัน แถวที่เป็นตารางคือกราฟที่แต่ละจุดเป็นช่องในตาราง ต่อกับช่องบนล่างซ้ายขวา น้ำหนักสุ่ม 1 ถึง 9 ซึ่งหน้า 28.3 จะเขียนให้ดู

กราฟ	น้อยสุดก่อน	มากสุดก่อน (ลืม greater)
สุ่ม V = 10⁴, E = 2 × 10⁴	0.002 วินาที	0.001 วินาที
สุ่ม V = 10⁵, E = 2 × 10⁵	0.029 วินาที	0.027 วินาที
ตาราง 100 × 100	0.001 วินาที ประมวลผล 10000 ครั้ง	2.526 วินาที ประมวลผล 66381539 ครั้ง
ตาราง 150 × 150	ไม่ได้วัด	14.611 วินาที ประมวลผล 351534020 ครั้ง (วัดรอบเดียว)

กราฟสุ่มไม่ฟ้องอะไรเลย เวลาพอๆ กัน แต่กราฟรูปตารางแค่หนึ่งหมื่นช่อง แบบมากสุดก่อนประมวลผลจุดซ้ำเฉลี่ยจุดละราวหกพันครั้ง ช้ากว่าหลายพันเท่า และตาราง 300 × 300 รอร้อยวินาทีแล้วยังไม่จบ ความผิดแบบนี้ตรวจด้วยตัวอย่างในโจทย์ไม่เจอ เพราะคำตอบถูก ทุกครั้งที่เขียน Dijkstra ให้เช็กบรรทัดประกาศคิวว่ามี greater

แบบที่ 3 เก็บระยะใน int

โจทย์บอกว่าน้ำหนักไม่เกิน 10⁹ ซึ่งอยู่ใน int หลายคนจึงเก็บระยะเป็น int ด้วย ลองถนนสามเส้นต่อกัน เส้นละ 10⁹

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

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});
    }
    vector<int> dist(n + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int u = 1; u <= n; u++) {
        cout << dist[u] << (u == n ? '\n' : ' ');
    }
    return 0;
}

4 3
1 2 1000000000
2 3 1000000000
3 4 1000000000

-294967296 -1294967296 -294967296 -1294967296

คำตอบที่ถูกคือ 0 1000000000 2000000000 3000000000 ซึ่งโปรแกรม dijkstra-pq ที่ใช้ long long ให้ถูกต้อง แต่แบบ int ระยะถึงจุด 4 คือ 3 × 10⁹ ล้นเป็น -1294967296 เลขเดียวกับตัวอย่างประชากรในหน้า 1.3 ค่าติดลบนั้นน้อยกว่าทุกอย่าง พอจุด 4 ถูกหยิบออกมาก็ผ่อนย้อนกลับไปจุด 3 จุด 2 และแม้แต่จุดเริ่ม ระยะของจุดเริ่มเองยังติดลบ ทางที่สั้นที่สุดยาวได้ถึง (V - 1) × น้ำหนักมากสุด ถ้าเกิน 2 × 10⁹ ต้องใช้ long long ทั้ง dist และช่องแรกของ pair ในคิว ส่วนน้ำหนักใน adj เก็บเป็น int ได้ เพราะ d + w เป็น long long บวก int ผลจึงเป็น long long

สรุป

ใส่คู่ (dist[v], v) ลง priority_queue แบบน้อยสุดก่อน ระยะลดลงเมื่อไรก็ใส่คู่ใหม่ ปล่อยคู่เก่าค้างไว้
หยิบออกมาแล้วถ้า d > dist[u] คือคู่เก่า ต้องข้าม ไม่งั้นอาจช้าระเบิด
ความซับซ้อน O((V + E) log V) ใช้กับกราฟเส้นน้อยที่ V เป็นแสนได้ กราฟที่ E ใกล้ V² แบบอาเรย์ไม่แพ้
ต้องใส่ greater ลืมแล้วคำตอบยังถูกแต่ช้า ตรวจด้วยตัวอย่างเล็กไม่เจอ
ระยะรวมเกิน int ได้ง่าย ใช้ long long ทั้งใน dist และในคิว