A20934. 子图最短路
填空题
困难
知识点
题目描述
子图最短路
题目描述
给定包含n个结点m条边的带权无向图G，结点依次以1,2,....n编号。第(1≤i≤m)条边连接编号为ui与vi的两个结点，权值为wi。
对于指定的1≤ℓ≤r≤n，按以下方式构造图G的子图G(ℓ,r):
- 保留G中编号在区间[ℓ,r]中的结点。删去其它编号不在[ℓ,r]中的结点以及与之相连的边。剩余的结点和边构成子图G(ℓ,r)。
对于G(ℓ,r)中的任意结点u,v应有l≤u,v≤r。记u,v在子图G(ℓ,r)上的最短距离为d(ℓ,r,u,v)。特殊地，若u,v在子图G(ℓ,r)上不连通，则认为d(ℓ,r,u,v)=0。
你需要求出
d(ℓ,r,u,v)对109取模的结果。
- 题目中的英文字母l使用了特殊写法ℓ，以避免英文字母l与数字1混淆。
输入格式
第一行，两个正整数n,m，表示结点数与边数。
接下来m行，第i(1≤i≤m)行包含三个正整数ui,vi,wi，表示一条连接结点ui,vi的权值为wi的边。
输出格式
输出一行，一个整数，表示
d(ℓ,r,u,v)对109取模的结果。
样例
输入样例 1
3 2
1 2 1
2 3 2输出样例 1
9输入样例 2
4 6
1 2 100
2 3 100
3 4 100
1 3 10
2 4 10
1 4 1输出样例 2
784数据范围
对于40%的测试点，保证2≤n≤20。
对于所有测试点，保证2≤n≤100,2≤m≤n(n-1)/2，1≤ui,vi≤n,1≤wi≤106。图中可能存在重边。
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
const int mod = 1e9;
int n, m;
int f[N][N];
int g[N][N];
int ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
f[i][j] = mod;
f[i][i] = 0;
}
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
f[u][v] = min(f[u][v], w);
f[v][u] = min(f[v][u], w);
}
for (int l = 1; l <= n; l++) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = f[i][j];
for (int r = l; r <= n; r++) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][r] + g[r][j]);
for (int i = l; i <= r; i++)
for (int j = i; j <= r; j++)
ans = (ans + g[i][j]) % mod;
}
}
printf("%d\n", ans);
return 0;
}
上一题
下一题