CodeForces-25 C Roads in Berland(Floyd+挿入点)
1548 ワード
解析:新規作成するパスごとに、そのパスが原図の最短パスに影響しないと仮定すると、前回の答えを継承します.そうしないと、まず(u,v)の最短パスを更新し、点対(u,v)にそれぞれ全図を挿入して更新し、結果を計算します.
#include
using namespace std;
const int N = 3e2 + 5;
int G[N][N];
void floyd(int n) {
int i, j, k;
for(k = 1; k <= n; k += 1) {
for(i = 1; i <= n; i += 1) {
for(j = 1; j <= n; j += 1)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
}
}
void update(int k, int n) {
int i, j;
for(i = 1; i <= n; i += 1) {
for(j = 1; j <= n; j += 1)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
}
long long getvalue(int n) {
int i, j;
long long res = 0;
for(i = 1; i <= n; i += 1) {
for(j = i + 1; j <= n; j += 1)
res += G[i][j];
}
return res;
}
long long pre,query[N];
int main() {
int n, k, i, j;
scanf("%d", &n);
for(i = 1; i <= n; i += 1) {
for(j = 1; j <= n; j += 1)
scanf("%d", &G[i][j]);
}
floyd(n);
pre=getvalue(n);
scanf("%d", &k);
int u, v, c;
for(i = 1; i <= k; i += 1) {
scanf("%d%d%d", &u, &v, &c);
if(G[u][v] > c) {
G[u][v] = G[v][u] = c;
update(u, n);
update(v, n);
pre = getvalue(n);
}
query[i] = pre;
}
for(i = 1; i <= k; i += 1)
printf("%lld%c", query[i], i < k ? ' ' : '
');
return 0;
}