## Nhận xét
- Nhìn sơ qua, ta thấy ngay ta phải dùng thuật toán [Floyd](https://viblo.asia/p/thuat-toan-floyd-warshall-GrLZDBng5k0) để giải quyết bài toán
- Dijkstra thì chỉ dùng cho một nguồn
- SPFA và Bellmand-Ford tương tự
- Nhưng mình phải giải như thế nào cho một bài toán đồ thị có tính **cập nhật online** theo thời điểm
- Lúc này, ta cần phải sắp xếp lại các thời điểm thay đổi và truy vấn của đồ thị (giống *Sweep line* và *Offline Query*)
## Hướng giải chung
- Ta sắp xếp lại các thời điểm thay đổi và truy vấn (Và tống những truy vấn đó vô một mảng lưu trũ <u>truy vấn</u>
- Ta duyệt qua toàn bộ truy vấn và cập nhật
- Nếu là truy vấn cập nhật thì cập nhật lại các giá trị `d[i][j]` với ý nghĩa là độ dài đường đi ngắn nhất từ $i$ đến $j$
- Còn nếu là truy vấn thì ta sẽ in ra `d[u][v]` và lưu kết quả vào `res[i]` ($i$ ở đây là thứ tự của truy vấn đang xét)
- Cuối cùng ta in ra các giá trị của mảng `res`
## Cách cập nhật lại đồ thị
- Trước khi đọc tiếp, các bạn hãy đọc bài viết về thuật toán Floyd.
- Sau đó thì ta thử suy ngẫm một chút rồi hẵng đọc tiếp
### Thuật toán
Với mỗi lần thêm đỉnh $u$
1. Ta xét giá trị nhỏ nhất giữa `dp[i][u]` và `w[i][u]` $\forall i \in [1, n]$ và đã được thêm
2. Ta duyệt hai vòng for `st` và `mid` và `t`
- Nếu nó đã được thêm thì xét `d[i][u] = min(d[i][u], w[i][u]);`
3. Cuối cùng là for `i` và `j` là các điểm st và end
- Nếu cả hai đã thêm thì ta gán `d[i][j] = min(d[i][j], d[i][u] + d[u][j]);`
**Chú ý:** Khi cập nhật cho `d[u][v]` thì phải cập nhật cho `d[v][u]` (cập nhật hai chiều)
### Code tham khảo
```cpp
#include <bits/stdc++.h>
#define int long long
#define taskname "main"
#define debug(a, l, r) for (int _i = l; _i <= r; _i++) cout<<(a)[_i]<<' '; cout<<'\n'
#define debug_m(a, li, lj, ri, rj) for (int _i = li; _i <= ri; _i++){for (int _j = lj; _j <= rj; _j++) cout<<(a)[_i][_j]<<' '; cout<<'\n';} cout<<'\n'
using namespace std;
const int
maxN = 500,
maxQ = 1e5;
const long long oo = 1e18;
int n, m, q,
vis[maxN + 1],
res[maxQ + 1],
d[maxN + 1][maxN + 1],
w[maxN + 1][maxN + 1];
struct Query
{
int type, u, v, t, i;
void read_node(int _i)
{
cin>>t;
type = 1;
u = i = _i;
}
void read_query(int _i)
{
cin>>u>>v>>t;
type = 2;
i = _i;
}
bool operator < (const Query &other)const
{
return t < other.t || t == other.t && type < other.type;
}
}listq[maxQ + 1];
void finit_node_edge()
{
cin>>n>>m;
for (int i = 1; i <= n; i++)
listq[i].read_node(i);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
{
w[i][j] = oo;
d[i][j] = oo;
}
}
}
for (int i = 1; i <= m; i++)
{
int u, v, c; cin>>u>>v>>c;
w[u][v] = c;
w[v][u] = c;
}
}
void finit_query()
{
cin>>q;
for (int i = 1; i <= q; i++)
listq[i + n].read_query(i);
q += n;
sort(listq + 1, listq + q + 1);
}
void add_e(int u){
vis[u] = true;
for (int i = 1; i <= n; i++)
{
if (vis[i])
{
d[i][u] = min(d[i][u], w[i][u]);
d[u][i] = d[i][u];
}
}
for (int mid = 1; mid <= n; mid++)
{
for (int st = 1; st <= n; st++)
{
if (vis[st] && vis[mid])
{
d[st][u] = min(d[st][u], d[st][mid] + d[mid][u]);
d[u][st] = d[st][u];
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (vis[i] && vis[j])
{
d[i][j] = min(d[i][j], d[i][u] + d[u][j]);
d[j][i] = d[i][j];
}
}
}
}
void solve(){
for (int i = 1; i <= q; i++)
{
if (listq[i].type == 1)
add_e(listq[i].u);
else res[listq[i].i] = d[listq[i].u][listq[i].v];
}
for (int i = 1; i <= q - n; i++)
cout<<(res[i] == oo ? -1 : res[i])<<'\n';
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(taskname".inp","r",stdin);
freopen(taskname".out","w",stdout);
#endif
finit_node_edge(); finit_query(); solve();
}
```
minhpnk2
Created at
1 likes