简答题
适中
#24858
子图最短路
子图最短路


答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#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;
}</pre>
这道题暂未补解析。