多源最短路 Floyd
题目传送门:传送门
今天写了一个题,对Floyd
的理解大大加深了,不得不说,这是个Floyd
的好题,如果对Floyd
理解不够深的话,可能无从下手,但是如果理解了Floyd
,这道题就非常简单了。
(复制粘贴出错了,不想改了 想看题面走传送门吧)
题目背景
BBB地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响。但是在村庄重建好之前,所有与未重建完成的村庄的公路均无法通车。换句话说,只有连接着两个重建完成的村庄的公路才能通车,只能到达重建完成的村庄。
题目描述
给出BBB地区的村庄数NNN,村庄编号从000到N−1N-1N−1,和所有MMM条公路的长度,公路是双向的。并给出第iii个村庄重建完成的时间tit_iti,你可以认为是同时开始重建并在第tit_iti天重建完成,并且在当天即可通车。若tit_iti为000则说明地震未对此地区造成损坏,一开始就可以通车。之后有QQQ个询问(x,y,t)(x, y, t)(x,y,t),对于每个询问你要回答在第ttt天,从村庄xxx到村庄y的最短路径长度为多少。如果无法找到从xxx村庄到yyy村庄的路径,经过若干个已重建完成的村庄,或者村庄xxx或村庄yyy在第t天仍未重建完成 ,则需要返回−1-1−1。
输入格式
第一行包含两个正整数N,MN,MN,M,表示了村庄的数目与公路的数量。
第二行包含NNN个非负整数t0,t1,…,tN−1,表示了每个村庄重建完成的时间,数据保证了t0≤t1≤…≤tN−1。
接下来M行,每行333个非负整数i,j,wi, j, wi,j,w,www为不超过10000的正整数,表示了有一条连接村庄iii与村庄j的道路,长度为www,保证i≠j,且对于任意一对村庄只会存在一条道路。
接下来一行也就是M+3行包含一个正整数Q,表示Q个询问。
接下来Q行,每行333个非负整数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
说明/提示
N≤200
M≤N×(N−1)/2
Q≤50000
我们先来看Floyd的核心代码:
1 | for (int k = 1; k <= n; k++) |
相信这个代码都很熟悉了,Floyd算法最本质的思想,其实就是用前k个点来更新i到j的距离。
再回到这个题目,我们只需按照城市的修复时间排序(当然,这题给出的时间就是有序的),然后再用前面已经修复的k个点来更新就行了。
代码如下:
1 | ll tt[210]; |
参考大佬博客:传送门