Codeforces Beta Round #25 C 题 Roads in Berland

发表于 分类于

这题很囧的 7、8 次 WA 都贡献给了 I64d。。。好吧我承认这个 CF 很强大。。。

这题的思路如下：

首先用 Floyd 在 O(n3)O(n^3) 的时间复杂度内算出最短路总和 retret

更新的边 (x,y)(x, y) 长度是 ww，那么如果 w≥dist[x][y]w \geq dist[x][y] 就不做处理，输出这时的 retret

如果 w<dist[x][y]w<dist[x][y]，那么枚举所有的结点，对结点 jj 和 kk

dist[j][k]dist[j][k] 的值就是 dist[j][k]dist[j][k]、dist[j][x]+w+dist[y][k]dist[j][x]+w+dist[y][k] 和 dist[j][y]+w+dist[x][k]dist[j][y]+w+dist[x][k] 中的最小值。

如果 dist[j][k]dist[j][k] 的新值比原来的小，那么就更新 retret 的值。

为了优化时间，让 jj 大于 ii，更新了 dist[j][k]dist[j][k] 后顺便把 dist[k][j]dist[k][j] 更新了

dist[k][j]=dist[j][k]dist[k][j]=dist[j][k]

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;
typedef long long LL;

const int MAX = 310;

int p, q, k, n;
LL dist[MAX][MAX];

void Floyd() {
  for (k = 1; k <= n; k++)
    for (p = 1; p <= n; p++)
      for (q = 1; q <= n; q++)
        if (dist[p][q] - dist[p][k] > dist[k][q])
          dist[p][q] = dist[p][k] + dist[k][q];
}

int main() {
  int m;
  int x, y, w, tmp;
  LL ret = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      scanf("%I64d", &dist[i][j]);
    }
  }
  Floyd();
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) ret += dist[i][j];
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &x, &y, &w);
    if (x > y) swap(x, y);
    if (w < dist[x][y]) {
      for (int j = 1; j <= n; j++) {
        for (int k = j + 1; k <= n; k++) {
          tmp = dist[j][k];
          if (dist[j][x] + w + dist[y][k] < dist[j][k])
            dist[j][k] = dist[j][x] + w + dist[y][k];
          if (dist[j][y] + w + dist[x][k] < dist[j][k])
            dist[j][k] = dist[j][y] + w + dist[x][k];
          if (dist[j][k] < tmp) {
            ret -= tmp - dist[j][k];
            dist[k][j] = dist[j][k];
          }
        }
      }
    }
    if (i) printf(" ");
    printf("%I64d", ret);
  }
  printf("\n");
  return 0;
}

总结：关于最短路中改变一条边权值的问题，可以通过边的两个顶点来进行更新