对以下c++代码进行改编但不改变代码准确性:#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; typedef long long LL; const int N = 105, M = 2505, L = 20; const LL INF = 1e18; int n, m, K, l; LL d[N][N], w[N][N], g[L][N][N], f[N], t[N]; struct E{ int u, v, w; } e[M]; int main() { memset(g, 0x3f, sizeof g); scanf("%d%d%d", &n, &m, &K); l = log2(K); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j) d[i][j] = INF; for (int i = 1; i <= m; i++) { scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); d[e[i].u][e[i].v] = min(d[e[i].u][e[i].v], (LL)e[i].w); } for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { w[i][j] = d[i][j]; for (int k = 1; k <= m; k++) w[i][j] = min(w[i][j], d[i][e[k].u] - e[k].w + d[e[k].v][j]); g[0][i][j] = w[i][j]; } } for (int c = 1; c <= l; c++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) g[c][i][j] = min(g[c][i][j], g[c - 1][i][k] + g[c - 1][k][j]); for (int i = 1; i <= n; i++) f[i] = d[1][i]; for (int c = 0; c <= l; c++) { if (K >> c & 1) { for (int i = 1; i <= n; i++) t[i] = f[i]; memset(f, 0x3f, sizeof f); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i] = min(f[i], t[j] + g[c][j][i]); } } printf("%lld\n", f[n]); return 0; }
时间: 2023-12-30 16:05:55 浏览: 34
#include <iostream>
#include <cstdio>
#include <cmath>
#include <>
using namespace std; typedef long long LL const int N = 105, M = 2505, L = 20;
const LL INF = 1e18; int n, m, K, l;
LL d[N][N], w[N][N], g[L][N][N], f[N], t[N]; struct E{
int u, v, w;
} e[M]; int main() {
memset(g, 0x3f, sizeof g);
scanf("%d%d%d", &n, &m, &K);
l = log2(K);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) if (i != j) d[i][j] = INF;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
d[e[i].u][e[i].v] = min(d[e[i].u][e[i].v], (LL)e[i].w);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = d[i][j];
for (int k = 1; k <= m; k++)
w[i][j] = min(w[i][j], d[i][e[k].u] - e[k].w + d[e[k].v][j]);
g[0][i][j] = w[i][j];
}
}
for (int c = 1; c <= l; c++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
g[c][i][j] = min(g[c][i][j], g[c - 1][i][k] + g[c - 1][k][j]);
for (int i = 1; i <= n; i++) f[i] = d[1][i];
for (int c = 0; c <= l; c++) {
if (K >> c & 1) {
for (int i = 1; i <= n; i++) t[i] = f[i];
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) f[i] = min(f[i], t[j] + g[c][j][i]);
}
}
printf("%lld\n", f[n]);
return 0;
}