洛谷P1119《灾后重建》

一月 22, 2019 5955

让人加深对 Floyd 的理解

题目背景

B地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述

给出B地区的村庄数 N ，村庄编号从 0 到 N−1 ，和所有 M 条公路的长度，公路是双向的。并给出第 i 个村庄重建完成的时间 t_i ，你可以认为是同时开始重建并在第 t_i ​ 天重建完成，并且在当天即可通车。若 t_i ​为 0 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 Q 个询问 (x, y, t) ，对于每个询问你要回答在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少。如果无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村庄，或者村庄 x 或村庄 y 在第 t 天仍未重建完成 ，则需要返回 -1 。

输入输出格式

输入格式

第一行包含两个正整数 N,M ，表示了村庄的数目与公路的数量。

第二行包含 N 个非负整数 t_0, t_1,…, t_{N-1} ，表示了每个村庄重建完成的时间，数据保证了 t_0 ≤ t_1 ≤ … ≤ t_{N-1} 。

接下来 M 行，每行 3 个非负整数 i, j, w ， w 为不超过 10000 的正整数，表示了有一条连接村庄 i 与村庄 j 的道路，长度为 w ，保证 i≠j ，且对于任意一对村庄只会存在一条道路。

接下来一行也就是 M+3 行包含一个正整数 Q ，表示 Q 个询问。

接下来 Q 行，每行 3 个非负整数 x, y, t ，询问在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少，数据保证了 t 是不下降的。

输出格式

共 Q 行，对每一个询问 (x, y, t) 输出对应的答案，即在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少。如果在第 t 天无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村庄，或者村庄 x 或村庄 y 在第 t 天仍未修复完成，则输出 -1 。

输入输出样例

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4

输出样例

1
2
3
4
-1
-1
5
4

说明

对于 30\% 的数据，有 N≤50 ；

对于 30\% 的数据，有 t_i= 0 ​，其中有 20\% 的数据有 t_i = 0 且 N>50 ；

对于 50\% 的数据，有 Q≤100 ；

对于 100\% 的数据，有 N≤200 ， M≤N \times (N-1)/2 ， Q≤50000 ，所有输入数据涉及整数均不超过 100000 。

解题思路

首先 N \leq 200 ，那么肯定是用 Floyd

Floyd 算法的本质是 DP，转移方程为

f_{i,j} = min(f_{i,j},\ f_{i,k} + f_{k,j})

其中的这个 k 就是「中转点」，表示当前最大能经过编号为 k 的点。

明确了这些，我们再来看题。

给出每一个点状态转为「可用」的时间和所有的边，让你求任意点到点的距离。
我们跑 Floyd 时， k 限制了我们当前能走的点，就相当于是题目中点的「不可用」状态！再加上所有的询问都是按照时间顺序给出的，所以我们就可以利用 Floyd 的性质来做这题。

1
2
/* -- 全局变量 -- */
int now = 0; // 当前最多能走第 now 个点，也就是 Floyd 中的 k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* -- 在函数 main() 里 -- */

std::cin >> start >> end >> ti// 读入起止点 start end 和当前时间 ti

while (Time[now] <= ti) {
	// 当前的点转为「可用」的时间没有超过当前时间
	
	int k = now; // 方便理解
	// 以下为标准的 Floyd
	for (int x = 0; x < n; ++x) {
		for (int y = 0; y < n; ++y) {
			dis[x][y] = std::min(dis[x][y], dis[x][k] + dis[k][y]);
		}
	}
	++now; // 这个点更新完了，往后继续更新，直到超过当前时间
}
if (
	dis[start][end] == __INF /* 无法到达 */ 
	|| Time[start] > ti 
	|| Time[end] > ti /* 没有转为「可用」 */
) puts("-1");
else printf("%d\n", dis[start][end]); // 输出答案

代码实现

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXN = 1000 + 10;
        
    int dis[MAXN][MAXN], k;

    int n, m, q;
    int ttime[MAXN];
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    using FastIO::getint;
    n = getint();
    m = getint();
    memset(ttime, 0x3f, sizeof ttime);
    memset(dis, 0x3f, sizeof dis);
    for (int i = 0; i < n; ++i) {
        ttime[i] = getint();
    }
    for (int i = 1; i <= m; ++i) {
        int prev = getint();
        int next = getint();
        int weight = getint();
        dis[prev][next] = dis[next][prev] = weight;
    }
    for (int i = 0; i <= n; ++i) dis[i][i] = 0;
    q = getint();
    for (int i = 1; i <= q; ++i) {
        int s = getint();
        int t = getint();
        int timee = getint();
        int ans = 0;
        while (ttime[k] <= timee) {
            for (int a = 0; a < n; ++a) {
                for (int b = 0; b < n; ++b) {
                    dis[a][b] = std::min(dis[a][b], dis[a][k] + dis[k][b]);
                }
            }
            ++k;
        }
        if (dis[s][t] == 0x3f3f3f3f || ttime[s] > timee || ttime[t] > timee) ans = -1;
        else ans = dis[s][t];
        printf("%d\n", ans);
    }
    return 0;
}