Cho n thành phố, m đường (u,v,w). Bộ ba (s,t,k): đường đi từ s đến t chỉ qua thành phố 1..k. Tính tổng độ dài đường đi ngắn nhất cho mọi bộ ba (s,t,k). Nếu không đến được cộng 0.
Ví dụ
Với n=4, m=2, edges={{1,2,5},{2,3,4},{3,4,3}}, đầu ra 63.
Giải thuật
Floyd-Warshall biến thể: thêm đỉnh trung gian theo thứ tự 1..n. Khởi tạo ma trận khoảng cách. Với k=1..n: cập nhật d[i][j] = min(d[i][j], d[i][k]+d[k][j]). Sau mỗi k, cộng tất cả d[i][j] != INF vào kết quả.
Mã 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]), b = get<1>(edges[i]), 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;
}
Đầu vào / Đầu ra
Input: 4, 2, {{1,2,5},{2,3,4},{3,4,3}}
Output: 63