## Thuật toán ngây thơ
Xét mọi phương án gán trọng số của một cạnh $(u, v)$ bằng $0$. Mỗi phương án như vậy, ta sử dụng thuật toán Floyd để tìm đường đi ngắn nhất giữa mọi cặp đỉnh từ đó ghi nhận lại giá trị nhỏ nhất của biểu thức cần tính.
**Độ phức tạp.** $O(m\times n^3)$
## Cải tiến
Sử dụng thuật toán Floyd để tính mảng $\texttt{d[i][j]}$ là độ dài dường đi ngắn nhất từ $i$ đến $j$.
Với mỗi phương án gán trọng số của một cạnh $(u, v)$ bằng $0$, để đi từ $i$ đến $j$ ta có các phương án sau:
- Không đi qua cạnh này: Chi phí là $\texttt{d[i][j]}$
- Đi theo lộ trình $i \rightarrow u \rightarrow v \rightarrow j$: Chi phí là $\texttt{d[i][u]} + \texttt{d[v][j]}$
- Đi theo lộ trình $i \rightarrow v \rightarrow u \rightarrow j$: Chi phí là $\texttt{d[i][v]} + \texttt{d[u][j]}$
Khi đó ta có thể tính lại mảng $d$ chỉ trong $O(n^2)$.
**Độ phức tạp.** $O(n^3 + m\times n^2)$.
## Cài đặt tham khảo
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long INF = 1e18 + 7;
const int MAXN = 105;
int n, m;
long long w[MAXN][MAXN], d[MAXN][MAXN];
long long floyd(int a, int b) {
long long res = 0;
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
long long cur = d[i][j];
cur = min(cur, d[i][a] + d[b][j]);
cur = min(cur, d[i][b] + d[a][j]);
res += cur;
}
}
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
w[i][j] = INF;
for (int i = 1; i <= m; ++i) {
int u, v, weight; cin >> u >> v >> weight;
w[u][v] = min(w[u][v], (long long)weight);
w[v][u] = min(w[v][u], (long long)weight);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
d[i][j] = w[i][j];
if (i == j) d[i][j] = 0;
}
}
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (d[i][k] < INF && d[k][j] < INF)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
long long ans = 1e18 + 7;
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
ans = min(ans, floyd(i, j));
}
}
cout << ans;
return 0;
}
```
chithanhnguyen
Created at
1 likes