HDU 5636 Shortest Path

发表于 | 分类于 |

链接

传送门

题意

有一条长度为$n$的链，相邻的点之间的距离为1，再给出三条额外的边长度也为1。给出$m$组查询，查询$u$到$v$之间的距离，输出$S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)$，$z_i$是第$i$次查询的结果。

思路

预处理出新加的边所连的点间的最段路，对于每次查询，枚举是否可以用新加的边的端点获得更短路径。

代码

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
const int maxn = 6;
int a[maxn];
int d[maxn][maxn];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < maxn; i += 2) {
      scanf("%d%d", &a[i], &a[i + 1]);
      d[i][i + 1] = d[i + 1][i] = min(d[i][i + 1], 1);
    }
    for (int i = 0; i < maxn; ++i) {
      for (int j = i + 1; j < maxn; ++j) {
        d[i][j] = d[j][i] = min(d[i][j], abs(a[i] - a[j]));
      }
    }
    for (int k = 0; k < maxn; ++k) {
      for (int i = 0; i < maxn; ++i) {
        for (int j = 0; j < maxn; ++j) {
          d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
      }
    }
    LL ans = 0LL;
    for (int i = 1; i <= m; ++i) {
      int u, v;
      scanf("%d%d", &u, &v);
      LL len = abs(u - v);
      for (int j = 0; j < maxn; ++j) {
        for (int k = 0; k < maxn; ++k) {
          len = min(len, LL(abs(u - a[j]) + abs(v - a[k]) + d[j][k]));
        }
      }
      ans = (ans + len * i) % mod;
    }
    printf("%d\n", int(ans));
  }
  return 0;
}