[2019宁夏网络赛-F] Moving On

发表于 | 更新于 | 分类于 ， ，
本文字数： 10k

链接

\(\text{2019宁夏网络赛-F.Moving On}\)

题意

  有\(n\)个城市，城市\(i\)有一个犯罪值\(r_i\)，城市u和v之间的距离是\(d[i][j]\)(无向图)，现在有\(q\)次查询，每次查询询问从城市\(u\)到\(v\)，在中途经过的任意城市的犯罪值不超过\(w\)的情况下(中途城市不包括\(i\)和\(j\))的最短路径是多少。

  输入格式：共\(t\)组样例，每个测试样例的第一行\(n,q\)，代表\(n\)个城市，共\(q\)次查询，接下来一行\(n\)个整数\(r_1,r_2...r_n\)，接下来是一个\(n\times n\)的矩阵\(d\)，接下来\(q\)行代表\(q\)次查询，每行三个数\(u,v,w\).

  数据范围：\(t<50,1≤ri_​≤10^5,1≤d_{i,j}​≤10^5(ij),d_{i,i}​=0,d_{i,j}=d_{j,i},1\leq u,v\leq n,1\leq w\leq 10^5\).

  输出格式：每个测试样例的第一行输出Case #x:，x代表第x个测试样例，接下来的每一行输出一个询问结果。

分析

  题目给出了\(n\)个点，整个图是一个稠密图，并且有\(q\)次查询，即使每次查询都使用复杂度为\(\text{O((N+M)logN)}\)的堆优化的\(\text{Dijstra}\)也会超时。

  这里使用\(\text{floyd}\)，对于\(\text{floyd}\)求最短路来说，\(f[k][i][j]\)表示从\(i\)到\(j\)中途经过\(k\)的最短路，那么我们可以把城市按照犯罪值\(r[i]\)升序排列，那么\(f[k][i][j]\)则就是从\(i\)到\(j\)中途经过犯罪值前\(k\)小城市（意思是经过前\(k\)小城市中的一部分）的最短路，那么我们需要求出所有的答案，我们的\(f[k][i][j]\)可以通过从i到j中途经过犯罪值前k-1小城市（同上）的最短路以及从i到k和从k到j中途经过前k-1小城市（同上）的最短路的和，这二者更新得到。

  之后对于每个询问\((u,v,w)\)，二分找到满足犯罪值小于等于\(w\)的犯罪值最大的城市编号\(k\)，\(f[k][u][v]\)即是查询结果。

  1. 当图是个稠密图，并且询问多次两点之间最短路的时候可以使用Floyd算法； 2. 注意使用Floyd的任何变形；

代码

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
#include <bits/stdc++.h>
using namespace std;
int t, n, q, u, v, w;
int dp[205][205][205];
struct roberry{
    int va, id;
    bool operator<(const roberry & a)const{
        return a.va > va;
    }
}r[205];

int find(int w, int l1, int r1) {
    while (l1 + 1< r1) {
        int mid = (l1 + r1) >> 1;
        if (r[mid].va <= w)l1 = mid;
        else r1 = mid;
    }
    return l1;
}
int cnt;
int main() {
    scanf("%d", &t);
    while (t--) {
        printf("Case #%d:\n", ++cnt);
        memset(dp, 0, sizeof(dp));
        scanf("%d%d", &n, &q);
        for (int i = 1; i <= n; i++){
            scanf("%d", &r[i].va);
            r[i].id = i;
        }
        sort(r + 1, r + 1 + n);
        int x;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++){
                scanf("%d", &x);    
                dp[0][i][j] = x;
            }
        for (int i = 1; i <= n; i++){
            int p = r[i].id;
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= n; k++)
                    dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j][p] + dp[i - 1][p][k]);
        }
        while (q--) {
            scanf("%d%d%d", &u, &v, &w);
            printf("%d\n",dp[find(w, 0, n + 1)][u][v]);
        }
    }
}