โปรแกรม C++ หาผลรวมค่าใช้จ่ายเส้นทางสั้นที่สุดสำหรับทริปเล็ตทั้งหมด

คำอธิบายปัญหา

สมมติว่ามีเมือง n แห่ง และถนน m สาย ถนนให้มาในอาร์เรย์รูปแบบ {ต้นทาง, ปลายทาง, น้ำหนัก} กำหนดทริปเล็ต (s, t, k) โดย s, t, k เป็นเมือง ต้องคำนวณเวลาน้อยที่สุดจาก s ไป t โดยเยี่ยมชมได้เฉพาะเมือง 1 ถึง k ถ้า t ไม่ถึงได้จาก s คืน 0 ต้องคำนวณทุกทริปเล็ต (s, t, k) และหาผลรวม

ตัวอย่าง: n = 4, m = 2, edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}} ผลลัพธ์คือ 63

ขั้นตอนการแก้ปัญหา

กำหนดอาร์เรย์ 2D dvec เริ่มต้น infinity
สำหรับ i := 0 ถึง n-1: dvec[i,i] := 0
สำหรับ i := 0 ถึง m-1:
    a := edges[i] ตัวแรก
    b := edges[i] ตัวที่สอง
    c := edges[i] ตัวที่สาม
    ลด a,b ลง 1
    dvec[a,b] := c
res := 0
สำหรับ k := 0 ถึง n-1:
    สำหรับ i := 0 ถึง n-1:
        สำหรับ j := 0 ถึง n-1:
            dvec[i,j] := min(dvec[i,j], dvec[i,k] + dvec[k,j])
            ถ้า dvec[i,j] != infinity: res := res + dvec[i,j]
พิมพ์ res

ตัวอย่างโค้ด C++

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

const int INF = 1e9;
void solve(int n, int m, vector<tuple<int, int, int>> edges){
    vector<vector<int>> dvec(n, vector<int>(n, INF));
    for(int i = 0; i < n; i++) dvec[i][i] = 0;
    for(int i = 0; i < m; i++) {
        int a = get<0> (edges[i]);
        int b = get<1> (edges[i]);
        int c = get<2> (edges[i]);
        a--; b--;
        dvec[a][b] = c;
    }
    int res = 0;
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dvec[i][j] = min(dvec[i][j], dvec[i][k]+dvec[k][j]);
                if(dvec[i][j] != INF) res += dvec[i][j];
            }
        }
    }
    cout << res << endl;
}

int main() {
    int n = 4, m = 2;
    vector<tuple<int, int, int>> edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}};
    solve(n, m, edges);
    return 0;
}

อินพุต

4, 2, {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}

เอาต์พุต

63