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;
}

支付宝扫码领红包