Fork me on GitHub

【学习笔记】 luogu-P1119-灾后重建

发表于 | 更新于 | 分类于 |

今天小蒟蒻做了一道和最短路有关的题qwq （虽然是看的题解，但是受益匪浅啊qwq，作一篇笔记放在这里以后可以用来复习

题目大意的就是让我们从第零天开始，每一天都会更新一些村庄，这些村庄里面有路，但是呢因为有的没修好，所以只有两边都修好的路才能通，题目就是让我们对Q次询问每次都做出一个答案来

这个题一看就会想到Floyd啊（毕竟范围辣么小,但是呢我们需要在这上面修改一些东西，用一个数组t[k]来保存第k个村庄修好的时间，因为说了是顺序的，所以给我们减少了很多的麻烦，我们只需要在这基础上让k不断地递增就可以来判断是不是有dis值能使a到b

当然t数组的保存有两种办法，小蒟蒻选择的是题解的方法（才不会告诉你们我是看了半天才看的qwq，第一种是开始就给上面附上最大值，这样我们就可以不用在while循环里面判断是不是k<n啦qwq，还有一种就是直接for赋值但要在k递增的时候判断是不是越界了（没辣么多村庄你修辣么多干什么qwq

上代码

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define re register

using namespace std;

int dis[1001][1001],t[1000001],n,m,Q,k;

int main()
{
	memset(dis,0x3f,sizeof(dis));
	memset(t,0x3f,sizeof(t));
	scanf("%d%d",&n,&m);
	for(re int i=0; i<=n-1; i++) scanf("%d",&t[i]),dis[i][i]=0;
	for(re int i=1; i<=m; i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		dis[a][b]=dis[b][a]=c;
	}
	scanf("%d",&Q);
	for(re int i=1; i<=Q; i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		while(t[k]<=c)
		{
			for(re int i=0; i<=n-1; i++)
				for(re int j=0; j<=n-1; j++)
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			k++;
		}
		if(dis[a][b]==0x3f3f3f3f || t[a]>c || t[b]>c) printf("-1\n");
		else printf("%d\n",dis[a][b]);
	}
}
召唤蕾姆