[0]zero-index clytie0x/zero-index

28.6 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 ทางไปคลินิก

ระดับง่าย เวลาไม่เกิน 1 วินาที

หมู่บ้านแห่งหนึ่งมีจุดสำคัญ N จุด หมายเลข 1 ถึง N และมีถนน M เส้น ถนนแต่ละเส้นเชื่อมสองจุด วิ่งได้ทั้งสองทาง และใช้เวลาเดินทาง w วินาที บ้านของน้องอยู่ที่จุด 1 คลินิกอยู่ที่จุด N ให้หาว่าเดินทางจากบ้านไปคลินิกใช้เวลาน้อยที่สุดกี่วินาที ถ้าไม่มีทางไปถึงคลินิกเลยให้ตอบ -1

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000 และ 1 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงถนนระหว่างจุด u กับจุด v ใช้เวลา w วินาที โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ 1 ≤ w ≤ 109 จุดคู่เดียวกันอาจมีถนนเชื่อมมากกว่าหนึ่งเส้น

ข้อมูลออก

เวลาที่น้อยที่สุดเป็นวินาที หรือ -1 ถ้าไปไม่ถึง

6 9
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
3 5 10
4 5 2
4 6 6
5 6 3
13
5 3
1 2 7
2 3 4
4 5 1
-1
ดูคำใบ้

ถนนมีเวลาไม่เท่ากัน BFS จึงใช้ไม่ได้ ใช้ Dijkstra แบบ priority_queue ในหน้า 28.2 N ถึงแสน แบบอาเรย์ในหน้า 28.1 ไม่ทัน เวลารวมยาวได้ถึงราว 1014 วินาที ต้องเก็บระยะเป็น long long และใช้อนันต์ที่บวกแล้วไม่ล้น ถ้าจบแล้วระยะของจุด N ยังเป็นอนันต์ ให้ตอบ -1 ถนนซ้ำคู่ไม่ต้องทำอะไรพิเศษ Dijkstra ผ่อนทุกเส้นอยู่แล้ว

ดูเฉลย 
#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;
    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});
            }
        }
    }
    cout << (dist[n] == INF ? -1 : dist[n]) << '\n';
    return 0;
}

ข้อ 2 เวลาส่งพัสดุ

ระดับง่าย เวลาไม่เกิน 1 วินาที

เมืองแห่งหนึ่งมีทางแยก N แห่ง หมายเลข 1 ถึง N และมีถนนเดินรถทางเดียว M เส้น ถนนเส้นที่ i วิ่งจากทางแยก u ไปทางแยก v ได้ทางเดียว ใช้เวลา w วินาที ศูนย์กระจายพัสดุตั้งอยู่ที่ทางแยก S รถส่งของออกจากศูนย์ และต้องรู้ว่าไปถึงทางแยกแต่ละแห่งได้เร็วที่สุดภายในกี่วินาที เพื่อใช้ประกาศเวลาส่งให้ลูกค้า

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N M และ S คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000, 1 ≤ M ≤ 200000 และ 1 ≤ S ≤ N

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงถนนจากทางแยก u ไปทางแยก v ใช้เวลา w วินาที โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ 1 ≤ w ≤ 109

ข้อมูลออก

บรรทัดเดียว มีจำนวนเต็ม N ตัวคั่นด้วยช่องว่าง ตัวที่ i คือเวลาที่น้อยที่สุดจากทางแยก S ไปทางแยก i ถ้าไปไม่ถึงให้พิมพ์ -1 เวลาของทางแยก S เองคือ 0

5 6 2
2 1 4
2 3 1
3 1 2
1 4 7
4 2 3
5 4 1
3 0 1 10 -1
ดูคำใบ้

ถนนเป็นทางเดียว ใส่เฉพาะ adj[u] แล้วรัน Dijkstra แบบ priority_queue จากจุด S ครั้งเดียว ได้ระยะของทุกจุดพร้อมกัน ระยะเกิน int ได้ จุดที่ระยะยังเป็นอนันต์ให้พิมพ์ -1 พิมพ์คั่นด้วยช่องว่างหนึ่งช่อง ไม่มีช่องว่างท้ายบรรทัด

ดูเฉลย 
#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, start;
    cin >> n >> m >> start;
    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});
    }
    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[start] = 0;
    pq.push({0, start});
    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] == INF ? -1 : dist[u]) << (u == n ? '\n' : ' ');
    }
    return 0;
}

ข้อ 3 เส้นทางรถนำเที่ยว

ระดับง่าย เวลาไม่เกิน 1 วินาที

บริษัทนำเที่ยวกำลังวางเส้นทางรถบัสจากสนามบินไปโรงแรม จังหวัดนี้มีจุดแวะ N จุด หมายเลข 1 ถึง N สนามบินคือจุด 1 โรงแรมคือจุด N มีถนน M เส้น แต่ละเส้นเชื่อมสองจุด วิ่งได้ทั้งสองทาง ใช้เวลา w วินาที บริษัทต้องการเส้นทางที่ใช้เวลาน้อยที่สุด และต้องพิมพ์ลำดับจุดที่รถผ่านลงในตั๋วด้วย

รับประกันว่าถ้าไปถึงโรงแรมได้ เส้นทางที่ใช้เวลาน้อยที่สุดมีเพียงเส้นเดียว

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000 และ 1 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงถนนระหว่างจุด u กับจุด v ใช้เวลา w วินาที โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ 1 ≤ w ≤ 109

ข้อมูลออก

ถ้าไปไม่ถึงโรงแรม ให้พิมพ์ -1 บรรทัดเดียว

ถ้าไปถึง บรรทัดแรกคือเวลาที่น้อยที่สุด บรรทัดที่สองคือหมายเลขจุดที่รถผ่านตามลำดับ ตั้งแต่ 1 จนถึง N คั่นด้วยช่องว่าง

6 9
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
3 5 10
4 5 2
4 6 6
5 6 3
13
1 3 2 4 5 6
4 2
1 2 5
3 4 5
-1
ดูคำใบ้

Dijkstra แบบ priority_queue พร้อมจด parent[v] = u ทุกครั้งที่ผ่อนสำเร็จ แบบหน้า 28.3 จบแล้วเดินย้อนจากจุด N ตาม parent จนถึงจุด 1 แล้ว reverse ก่อนพิมพ์ ระยะรวมเกิน int ได้ และถ้าไปไม่ถึงให้พิมพ์ -1 บรรทัดเดียว ไม่ต้องพิมพ์บรรทัดที่สอง

ดูเฉลย 
#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);
    vector<int> parent(n + 1, 0);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, 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;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    if (dist[n] == INF) {
        cout << -1 << '\n';
        return 0;
    }
    vector<int> path;
    for (int u = n; u != 0; u = parent[u]) {
        path.push_back(u);
    }
    reverse(path.begin(), path.end());
    cout << dist[n] << '\n';
    for (int i = 0; i < (int)path.size(); i++) {
        cout << path[i] << (i + 1 == (int)path.size() ? '\n' : ' ');
    }
    return 0;
}

ข้อ 4 ศูนย์พักพิงที่ใกล้ที่สุด

ระดับกลาง เวลาไม่เกิน 1 วินาที

อำเภอหนึ่งมีหมู่บ้าน N แห่ง หมายเลข 1 ถึง N และมีถนน M เส้น แต่ละเส้นเชื่อมสองหมู่บ้าน วิ่งได้ทั้งสองทาง ใช้เวลา w วินาที ในอำเภอมีศูนย์พักพิงตั้งอยู่ในหมู่บ้าน K แห่ง เมื่อน้ำท่วม ทุกคนจะอพยพไปศูนย์ที่ไปถึงได้เร็วที่สุดจากหมู่บ้านของตัวเอง

ทางอำเภอต้องการรู้สองอย่าง อย่างแรกคือในบรรดาหมู่บ้านที่ไปถึงศูนย์ใดศูนย์หนึ่งได้ หมู่บ้านที่ต้องใช้เวลาอพยพนานที่สุดใช้เวลากี่วินาที อย่างที่สองคือมีกี่หมู่บ้านที่ไปไม่ถึงศูนย์ไหนเลย หมู่บ้านที่มีศูนย์อยู่แล้วใช้เวลาอพยพ 0 วินาที

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N M และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000 และ 1 ≤ K ≤ N

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงถนนระหว่างหมู่บ้าน u กับหมู่บ้าน v ใช้เวลา w วินาที โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ 1 ≤ w ≤ 109

บรรทัดสุดท้ายมีจำนวนเต็ม K ตัว คือหมายเลขหมู่บ้านที่มีศูนย์พักพิง หมายเลขอาจซ้ำกันได้

ข้อมูลออก

บรรทัดเดียว มีจำนวนเต็มสองตัวคั่นด้วยช่องว่าง ตัวแรกคือเวลาอพยพที่นานที่สุดในบรรดาหมู่บ้านที่ไปถึงศูนย์ได้ ตัวที่สองคือจำนวนหมู่บ้านที่ไปไม่ถึงศูนย์ไหนเลย

8 9 2
1 2 7
2 3 4
3 4 6
4 5 3
5 6 5
6 7 2
7 8 9
2 7 15
3 6 8
2 6
11 0
6 3 2
1 2 5
2 3 5
4 5 1
1 1
10 3
ดูคำใบ้

รัน Dijkstra จากศูนย์ทีละแห่งแล้วเก็บค่าน้อยสุด ใช้เวลา K เท่าของ Dijkstra หนึ่งครั้ง ซึ่งไม่ทันเมื่อ K เป็นพัน ให้ใส่ทุกศูนย์ลงคิวด้วยระยะ 0 ตั้งแต่แรก แบบหลายจุดเริ่มในหน้า 28.3 แล้วรันครั้งเดียว จบแล้วไล่ดูทุกหมู่บ้าน หาค่ามากสุดในบรรดาที่ไม่ใช่อนันต์ และนับตัวที่เป็นอนันต์ ระยะเกิน int ได้ และหมายเลขศูนย์อาจซ้ำ

ดูเฉลย 
#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, k;
    cin >> n >> m >> k;
    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;
    for (int i = 0; i < k; i++) {
        int shelter;
        cin >> shelter;
        if (dist[shelter] != 0) {
            dist[shelter] = 0;
            pq.push({0, shelter});
        }
    }
    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});
            }
        }
    }
    long long longest = 0;
    int stranded = 0;
    for (int u = 1; u <= n; u++) {
        if (dist[u] == INF) {
            stranded++;
        } else {
            longest = max(longest, dist[u]);
        }
    }
    cout << longest << ' ' << stranded << '\n';
    return 0;
}

ข้อ 5 ลุยทุ่งโคลน

ระดับง่าย เวลาไม่เกิน 1 วินาที

ทุ่งนาหลังฝนตกแบ่งเป็นตาราง R แถว C คอลัมน์ ช่องที่ยังเดินได้มีตัวเลขบอกแรงที่ต้องใช้เมื่อก้าวเข้าไปในช่องนั้น ยิ่งโคลนลึกยิ่งใช้แรงมาก ส่วนช่องที่เป็นบ่อน้ำเดินเข้าไปไม่ได้ ชาวนาอยู่ที่ช่องซ้ายบน ต้องไปที่ช่องขวาล่าง ก้าวได้ทีละช่องไปทางบน ล่าง ซ้าย หรือขวา แรงที่ใช้ทั้งหมดคือผลรวมของตัวเลขในทุกช่องที่ก้าวเข้าไป รวมช่องซ้ายบนที่ยืนอยู่ตอนเริ่มด้วย ถ้าเดินผ่านช่องเดิมซ้ำก็ต้องใช้แรงซ้ำ ให้หาแรงรวมที่น้อยที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม R และ C คั่นด้วยช่องว่าง โดยที่ 1 ≤ R, C ≤ 500

อีก R บรรทัด บรรทัดละ C จำนวน คั่นด้วยช่องว่าง แต่ละจำนวนเป็น -1 ถ้าช่องนั้นเป็นบ่อน้ำ หรือเป็นจำนวนเต็มตั้งแต่ 1 ถึง 109 ซึ่งคือแรงที่ใช้เมื่อก้าวเข้าช่องนั้น

ข้อมูลออก

แรงรวมที่น้อยที่สุด ถ้าไปถึงช่องขวาล่างไม่ได้ หรือช่องซ้ายบนหรือขวาล่างเป็นบ่อน้ำ ให้พิมพ์ -1 ถ้าตารางมีช่องเดียว คำตอบคือตัวเลขของช่องนั้น

4 6
1 3 9 1 1 2
1 -1 9 -1 9 1
1 1 2 1 1 -1
9 -1 1 1 1 1
10
3 3
1 1 -1
1 -1 1
-1 1 1
-1
ดูคำใบ้

ให้ช่อง (r, c) เป็นจุดหมายเลข r * C + c แล้วใช้ Dijkstra แบบตารางในหน้า 28.3 ระยะเริ่มของช่องแรกคือค่าของช่องแรก ไม่ใช่ 0 และน้ำหนักของการก้าวคือค่าของช่องที่ก้าวเข้าไป ข้ามช่องที่เป็น -1 ถ้าช่องเริ่มหรือช่องปลายเป็น -1 ตอบ -1 ได้ทันที ผลรวมเกิน int ได้ และตารางมีถึงสองแสนห้าหมื่นช่อง Dijkstra แบบอาเรย์ไม่ทัน

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows, cols;
    cin >> rows >> cols;
    vector<int> cost(rows * cols);
    for (int i = 0; i < rows * cols; i++) {
        cin >> cost[i];
    }
    int last = rows * cols - 1;
    if (cost[0] == -1 || cost[last] == -1) {
        cout << -1 << '\n';
        return 0;
    }
    vector<long long> dist(rows * cols, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[0] = cost[0];
    pq.push({dist[0], 0});
    while (!pq.empty()) {
        auto [d, id] = pq.top();
        pq.pop();
        if (d > dist[id]) {
            continue;
        }
        int r = id / cols, c = id % cols;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                continue;
            }
            int next = nr * cols + nc;
            if (cost[next] == -1) {
                continue;
            }
            if (d + cost[next] < dist[next]) {
                dist[next] = d + cost[next];
                pq.push({dist[next], next});
            }
        }
    }
    cout << (dist[last] == INF ? -1 : dist[last]) << '\n';
    return 0;
}

ข้อ 6 นับเส้นทางที่เร็วที่สุด

ระดับง่าย เวลาไม่เกิน 1 วินาที

แอปเรียกรถแห่งหนึ่งอยากรู้ว่าเส้นทางที่เร็วที่สุดจากจุดรับไปจุดส่งมีกี่แบบ เพื่อใช้กระจายรถไม่ให้กระจุกบนถนนเส้นเดียว แผนที่มีทางแยก N แห่ง หมายเลข 1 ถึง N และถนน M เส้น แต่ละเส้นเชื่อมสองทางแยก วิ่งได้ทั้งสองทาง ใช้เวลา w วินาที จุดรับคือทางแยก 1 จุดส่งคือทางแยก N

เส้นทางสองเส้นถือว่าต่างกันถ้าลำดับของถนนที่ใช้ต่างกัน ถ้ามีถนนสองเส้นเชื่อมทางแยกคู่เดียวกัน การใช้ถนนคนละเส้นก็นับเป็นคนละเส้นทาง ให้หาเวลาที่น้อยที่สุด และจำนวนเส้นทางที่ใช้เวลาน้อยที่สุดนั้น จำนวนอาจมากมาก จึงให้ตอบเศษจากการหารด้วย 1000000007

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000 และ 1 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงถนนระหว่างทางแยก u กับทางแยก v ใช้เวลา w วินาที โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ 1 ≤ w ≤ 109

ข้อมูลออก

ถ้าไปไม่ถึงทางแยก N ให้พิมพ์ -1 ถ้าไปถึง ให้พิมพ์จำนวนเต็มสองตัวคั่นด้วยช่องว่าง คือเวลาที่น้อยที่สุด และจำนวนเส้นทางที่ใช้เวลาเท่านั้น mod 1000000007

6 9
1 2 2
1 3 2
2 3 1
2 4 3
3 4 3
1 4 7
4 5 1
4 6 4
5 6 3
9 4
5 4
1 2 3
2 3 3
3 1 3
4 5 1
-1
ดูคำใบ้

Dijkstra แบบ priority_queue พร้อม ways แบบหน้า 28.3 ได้ระยะใหม่ที่น้อยกว่าเดิม ตั้ง ways[v] = ways[u] ได้ระยะเท่าเดิม บวก ways[u] แล้ว mod 1000000007 ต้องข้ามคู่เก่าเสมอ ไม่งั้นจุดที่ถูกหยิบซ้ำจะบวกจำนวนทางซ้ำ ระยะเกิน int ได้ และถนนซ้ำคู่ที่ยาวเท่ากันนับเป็นคนละทาง

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
const long long MOD = 1000000007;

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), ways(n + 1, 0);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[1] = 0;
    ways[1] = 1;
    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;
                ways[v] = ways[u];
                pq.push({dist[v], v});
            } else if (d + w == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    if (dist[n] == INF) {
        cout << -1 << '\n';
    } else {
        cout << dist[n] << ' ' << ways[n] << '\n';
    }
    return 0;
}

ข้อ 7 ไปส่งแล้ววนกลับ

ระดับกลาง เวลาไม่เกิน 1 วินาที

ร้านน้ำดื่มตั้งอยู่ที่ทางแยก 1 ในเมืองที่มีทางแยก N แห่ง หมายเลข 1 ถึง N และถนนเดินรถทางเดียว M เส้น ถนนแต่ละเส้นวิ่งจากทางแยก u ไปทางแยก v ได้ทางเดียว ใช้เวลา w วินาที ทุกทางแยกตั้งแต่ 2 ถึง N มีลูกค้าหนึ่งบ้าน วันนี้ต้องส่งน้ำให้ทุกบ้าน รถออกจากร้านไปส่งทีละบ้าน ส่งเสร็จแล้วต้องกลับมาที่ร้านก่อนออกไปบ้านถัดไป และทุกเที่ยววิ่งทางที่เร็วที่สุดทั้งขาไปและขากลับ

ให้หาเวลารวมของทุกเที่ยว คือผลรวมของ (เวลาที่น้อยที่สุดจากร้านไปบ้าน + เวลาที่น้อยที่สุดจากบ้านกลับร้าน) ของทุกบ้าน ถ้ามีบ้านใดที่รถไปไม่ถึงหรือกลับมาไม่ได้ ให้ตอบ -1

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000 และ 1 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงถนนจากทางแยก u ไปทางแยก v ใช้เวลา w วินาที โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ 1 ≤ w ≤ 106

ข้อมูลออก

เวลารวมของทุกเที่ยว หรือ -1

4 6
1 2 5
2 3 2
3 1 4
1 3 10
3 4 1
4 1 3
33
3 3
1 2 4
2 1 4
1 3 1
-1
ดูคำใบ้

ขาไปคือระยะจากจุด 1 ไปทุกบ้าน ได้จาก Dijkstra ครั้งเดียว ขากลับคือระยะจากทุกบ้านมาจุด 1 ซึ่งถ้ารัน Dijkstra จากทุกบ้านจะช้า N เท่า ให้สร้างกราฟอีกชุดที่กลับทิศถนนทุกเส้น ระยะจาก v มา 1 ในกราฟเดิมเท่ากับระยะจาก 1 ไป v ในกราฟกลับทิศ จึงรัน Dijkstra จากจุด 1 บนกราฟกลับทิศอีกครั้งเดียวก็ได้ขากลับของทุกบ้าน ผลรวมเกิน int และถ้าบ้านไหนไปไม่ถึงหรือกลับไม่ได้ ให้ตอบ -1

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

vector<long long> dijkstra(const vector<vector<pair<int, int>>> &adj, int start)
{
    int n = (int)adj.size() - 1;
    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[start] = 0;
    pq.push({0, start});
    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});
            }
        }
    }
    return dist;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> forward(n + 1), backward(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        forward[u].push_back({v, w});
        backward[v].push_back({u, w});
    }
    vector<long long> go = dijkstra(forward, 1);
    vector<long long> back = dijkstra(backward, 1);
    long long total = 0;
    for (int v = 2; v <= n; v++) {
        if (go[v] == INF || back[v] == INF) {
            cout << -1 << '\n';
            return 0;
        }
        total += go[v] + back[v];
    }
    cout << total << '\n';
    return 0;
}

ข้อ 8 รถขนสินค้าขากลับ

ระดับยาก เวลาไม่เกิน 1 วินาที

บริษัทรถบรรทุกมีโกดัง N แห่ง หมายเลข 1 ถึง N และเส้นทางวิ่ง M เส้น เส้นทางแต่ละเส้นวิ่งจากโกดัง u ไปโกดัง v ได้ทางเดียว มีค่าใช้จ่าย w บาท ถ้าวิ่งเส้นนั้นแล้วได้ค่าจ้างขนสินค้ามากกว่าค่าน้ำมัน ค่าใช้จ่ายจะติดลบ วิ่งเส้นทางเดิมซ้ำกี่ครั้งก็ได้ และทุกครั้งมีค่าใช้จ่ายเท่าเดิม

รถคันหนึ่งออกจากโกดัง 1 และต้องไปจบที่โกดัง N ให้หาค่าใช้จ่ายรวมที่น้อยที่สุด ระหว่างทางจะผ่านโกดังใดซ้ำกี่ครั้งก็ได้ รวมทั้งโกดัง N เองด้วย

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 2000 และ 1 ≤ M ≤ 5000

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงเส้นทางจากโกดัง u ไปโกดัง v มีค่าใช้จ่าย w บาท โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ -109 ≤ w ≤ 109

ข้อมูลออก

  • ถ้าไม่มีทางไปถึงโกดัง N ให้พิมพ์ unreachable
  • ถ้าทำให้ค่าใช้จ่ายรวมน้อยลงได้เรื่อยๆ ไม่สิ้นสุด ให้พิมพ์ -inf
  • นอกจากนั้นให้พิมพ์ค่าใช้จ่ายรวมที่น้อยที่สุด ซึ่งอาจติดลบได้
4 4
2 4 3
3 2 -4
1 3 5
1 2 2
4
5 5
1 2 4
2 3 -2
3 4 3
4 2 -2
4 5 1
-inf
ดูคำใบ้

มีค่าติดลบ Dijkstra ใช้ไม่ได้ ใช้ Bellman-Ford ในหน้า 28.4 N × M ไม่เกิน 107 ผ่อน V - 1 รอบแล้วตรวจต่ออีก V รอบ จุดที่ยังผ่อนได้และทุกจุดที่เดินต่อจากจุดพวกนั้นได้คือจุดที่ลดได้ไม่สิ้นสุด ถ้าจุด N อยู่ในพวกนี้ตอบ -inf ระวังวงติดลบที่ไปไม่ถึงจุด N หรือที่ไปจากจุด 1 ไม่ถึง สองแบบนี้ไม่มีผลกับคำตอบ ผ่อนเฉพาะถนนที่ต้นทางไปถึงแล้ว และคำตอบต่ำกว่าค่าน้อยสุดของ int ได้

ดูเฉลย 
#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<int> from(m), to(m), cost(m);
    for (int i = 0; i < m; i++) {
        cin >> from[i] >> to[i] >> cost[i];
    }
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;
        for (int i = 0; i < m; i++) {
            int u = from[i], v = to[i];
            if (dist[u] != INF && dist[u] + cost[i] < dist[v]) {
                dist[v] = dist[u] + cost[i];
                changed = true;
            }
        }
        if (!changed) {
            break;
        }
    }
    vector<bool> endless(n + 1, false);
    for (int round = 1; round <= n; round++) {
        for (int i = 0; i < m; i++) {
            int u = from[i], v = to[i];
            if (dist[u] == INF) {
                continue;
            }
            if (endless[u] || dist[u] + cost[i] < dist[v]) {
                endless[v] = true;
                dist[v] = min(dist[v], dist[u] + cost[i]);
            }
        }
    }
    if (dist[n] == INF) {
        cout << "unreachable" << '\n';
    } else if (endless[n]) {
        cout << "-inf" << '\n';
    } else {
        cout << dist[n] << '\n';
    }
    return 0;
}

ข้อ 9 เมืองนัดพบ

ระดับกลาง เวลาไม่เกิน 1 วินาที

เพื่อนร่วมรุ่น K คนนัดเจอกันช่วงปีใหม่ ประเทศนี้มีเมือง N เมือง หมายเลข 1 ถึง N และมีถนน M เส้น แต่ละเส้นเชื่อมสองเมือง วิ่งได้ทั้งสองทาง ใช้เวลา w นาที เพื่อนๆ ต้องเลือกเมืองนัดพบหนึ่งเมือง ซึ่งจะเป็นเมืองที่มีเพื่อนอยู่หรือไม่ก็ได้ ทุกคนเดินทางจากเมืองของตัวเองมาเมืองนัดพบด้วยทางที่เร็วที่สุด

ให้เลือกเมืองนัดพบที่ทำให้ผลรวมเวลาเดินทางของทุกคนน้อยที่สุด เมืองนัดพบต้องเป็นเมืองที่เพื่อนทุกคนเดินทางมาถึงได้ ถ้ามีหลายเมืองที่ผลรวมน้อยที่สุดเท่ากัน ให้เลือกเมืองที่หมายเลขน้อยที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N M และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 300, 0 ≤ M ≤ 50000 และ 1 ≤ K ≤ 1000

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงถนนระหว่างเมือง u กับเมือง v ใช้เวลา w นาที โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ 1 ≤ w ≤ 109 เมืองคู่เดียวกันอาจมีถนนเชื่อมมากกว่าหนึ่งเส้น

บรรทัดสุดท้ายมีจำนวนเต็ม K ตัว คือเมืองที่เพื่อนแต่ละคนอยู่ เพื่อนหลายคนอาจอยู่เมืองเดียวกัน

ข้อมูลออก

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

5 6 3
1 2 4
2 3 3
3 4 2
4 5 6
1 5 20
2 4 9
1 3 5
3 15
4 2 2
1 2 5
3 4 5
1 4
-1
ดูคำใบ้

N ไม่เกิน 300 ใช้ Floyd-Warshall ในหน้า 28.5 หาระยะทุกคู่ได้ใน 2.7 × 107 ขั้น แล้วลองทุกเมืองเป็นเมืองนัดพบ รวมระยะจากเมืองของเพื่อนทุกคน ข้ามเมืองที่มีเพื่อนคนใดไปไม่ถึง เริ่มตารางด้วยถนนที่สั้นที่สุดของแต่ละคู่ เพราะคู่เดียวกันอาจมีถนนหลายเส้น ลูป k ต้องอยู่นอกสุด ผลรวมเกิน int และอนันต์ต้องบวกกันแล้วไม่ล้น

ดูเฉลย 
#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, k;
    cin >> n >> m >> k;
    vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }
    for (int e = 0; e < m; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], (long long)w);
        d[v][u] = min(d[v][u], (long long)w);
    }
    for (int via = 1; via <= n; via++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][via] + d[via][j] < d[i][j]) {
                    d[i][j] = d[i][via] + d[via][j];
                }
            }
        }
    }
    vector<int> home(k);
    for (int i = 0; i < k; i++) {
        cin >> home[i];
    }
    int best_town = -1;
    long long best_total = INF;
    for (int town = 1; town <= n; town++) {
        long long total = 0;
        bool everyone = true;
        for (int i = 0; i < k; i++) {
            if (d[home[i]][town] == INF) {
                everyone = false;
                break;
            }
            total += d[home[i]][town];
        }
        if (everyone && total < best_total) {
            best_total = total;
            best_town = town;
        }
    }
    if (best_town == -1) {
        cout << -1 << '\n';
    } else {
        cout << best_town << ' ' << best_total << '\n';
    }
    return 0;
}

ข้อ 10 ตั๋วผ่านทางฟรีหนึ่งใบ

ระดับยาก เวลาไม่เกิน 1 วินาที

น้องได้รางวัลเป็นตั๋วผ่านทางฟรีหนึ่งใบ ใช้ได้กับถนนหนึ่งเส้นเท่านั้น ถนนเส้นที่ใช้ตั๋วจะไม่เสียค่าผ่านทางเลย ประเทศนี้มีเมือง N เมือง หมายเลข 1 ถึง N และมีถนน M เส้น แต่ละเส้นเชื่อมสองเมือง วิ่งได้ทั้งสองทาง ค่าผ่านทาง w บาท น้องอยู่เมือง 1 และจะไปเมือง N โดยจะใช้ตั๋วกับถนนเส้นใดก็ได้ไม่เกินหนึ่งเส้น ให้หาค่าผ่านทางรวมที่น้อยที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000 และ 1 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดละสามจำนวน u v w หมายถึงถนนระหว่างเมือง u กับเมือง v ค่าผ่านทาง w บาท โดยที่ 1 ≤ u, v ≤ N, u ≠ v และ 1 ≤ w ≤ 109

ข้อมูลออก

ค่าผ่านทางรวมที่น้อยที่สุด หรือ -1 ถ้าไปเมือง N ไม่ได้

6 9
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
3 5 10
4 5 2
4 6 6
5 6 3
4
4 2
1 2 5
3 4 5
-1
ดูคำใบ้

ลองทุกถนนเป็นถนนที่ใช้ตั๋วแล้วรัน Dijkstra ใหม่ทุกครั้ง ช้าไป M เท่า มีสองวิธีที่เร็ว วิธีแรก รัน Dijkstra จากจุด 1 ได้ from1 และจากจุด N ได้ fromN ถ้าใช้ตั๋วกับถนน u v คำตอบคือ from1[u] + fromN[v] ลองทุกถนนทั้งสองทิศแล้วเอาค่าน้อยสุด วิธีที่สอง ให้สถานะเป็น (จุด, ใช้ตั๋วไปแล้วหรือยัง) มี 2N สถานะ จากสถานะที่ยังไม่ใช้ตั๋ว เดินถนนแบบจ่ายเต็มหรือแบบใช้ตั๋วก็ได้ ส่วนสถานะที่ใช้ไปแล้วจ่ายเต็มอย่างเดียว แล้วรัน Dijkstra บนสถานะ ทั้งสองวิธีเป็น O((N + M) log N) ระวังอย่าให้ใช้ตั๋วได้สองครั้ง และระยะเกิน int

ดูเฉลย 
#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(2 * 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});
    while (!pq.empty()) {
        auto [d, state] = pq.top();
        pq.pop();
        if (d > dist[state]) {
            continue;
        }
        bool used = state > n;
        int u = used ? state - n : state;
        for (auto [v, w] : adj[u]) {
            int next = used ? n + v : v;
            if (d + w < dist[next]) {
                dist[next] = d + w;
                pq.push({dist[next], next});
            }
            if (!used && d < dist[n + v]) {
                dist[n + v] = d;
                pq.push({d, n + v});
            }
        }
    }
    long long answer = min(dist[n], dist[2 * n]);
    cout << (answer == INF ? -1 : answer) << '\n';
    return 0;
}