您的位置: 首页  >  IT文章  >  洛谷 P1119 灾后重建 floyd好题

洛谷 P1119 灾后重建 floyd好题

分类: IT文章 • 2022-05-22 00:13:18

题目背景

(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

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

-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 imes (N-1)/2)，(Q≤50000)，所有输入数据涉及整数均不超过(100000)。

思路

一开始我的思路停留在每一次询问更新一次最短路，因为每次我都要重新求一遍两个点的最短路，所以最快的算法就是(dijkstra)。一次更新的复杂度是(O(mlog_2 n))，一共有(Q)次询问，所以总时间复杂度就是(O(Qmlog_2 n))，而这个时间复杂度显然是不合格的，实际测试可以得(80pts)，吸氧也没用。

我记得有好多人说过，可以通过部分分的做法优化得到正解。然后我就思考了半天，发现询问时时间递增我没有用到，但还是不会优化(dijkstra)。然而正解是(floyd)...

而优化就是用到了查询时间时递增的特点（其实这只是一种提示，即使不提示也可以输入后存起来排序再求）。由于时间是递增的，我们可以每输入一个更大的时间时更新每两个点之间的最短路。而输入的时间也是递增的（同理可以存起来再排序）。我们可以用一个变量来记录当前位置，由于时间递增，所以询问时每输入一个时间恰好可以从记录的位置开始更新，每次更新就以这个点为中转点更新两点最短路，这样一次更新时间复杂度是(O(n^2))，每个点最多当一次中转点，也就是最多更新(n)次，那么总时间复杂度就是(O(n^3))，跟(Q)并没有关系，所以相当于是(O(n^3))预处理之后(O(1))查询，确实体现了(floyd)的灵活运用。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long int ll;
int n,m,q;
int f[210][210],t[210];
void floyd(int k){
	for(int i=0;i<n;i++){//注意此题从0开始
		for(int j=0;j<n;j++){
			if(f[i][k]+f[k][j]<f[i][j]){
				f[i][j]=f[i][k]+f[k][j];
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&t[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<=n;j++){
			f[i][j]=100000000;
		}
	}
	for(int i=0;i<n;i++){
		f[i][i]=0;
	}
	for(int i=1,x,y,z;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		f[x][y]=z;
		f[y][x]=z;
	}
	scanf("%d",&q);
	int now=0;//now记录当前位置
	while(q--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		while(t[now]<=z&&now<n){//能更新就全更新完，由于后面的时间会更宽裕，所以前面更新的一定也能更新，就不必再更新了，巧妙的优化
			floyd(now);
			now++;
		}
		if(t[y]>z||t[x]>z){//起点和终点都没有建好肯定不行
			printf("-1
");
			continue;
		}
		if(f[x][y]==100000000){//两点不能到达
			printf("-1
");
			continue;
		}
		printf("%d
",f[x][y]);
	}
	return 0;
}

相关推荐