題目背景

B地區(qū)在地震過后，所有村莊都造成了一定的損毀，而這場地震卻沒對公路造成什么影響。但是在村莊重建好之前，所有與未重建完成的村莊的公路均無法通車。換句話說，只有連接著兩個重建完成的村莊的公路才能通車，只能到達(dá)重建完成的村莊。

題目描述

給出B地區(qū)的村莊數(shù)N，村莊編號從0到N-1，和所有M條公路的長度，公路是雙向的。并給出第i個村莊重建完成的時間t[i]，你可以認(rèn)為是同時開始重建并在第t[i]天重建完成，并且在當(dāng)天即可通車。若t[i]為0則說明地震未對此地區(qū)造成損壞，一開始就可以通車。之后有Q個詢問(x, y, t)，對于每個詢問你要回答在第t天，從村莊x到村莊y的最短路徑長度為多少。如果無法找到從x村莊到y(tǒng)村莊的路徑，經(jīng)過若干個已重建完成的村莊，或者村莊x或村莊y在第t天仍未重建完成 ，則需要返回-1。

輸入輸出格式

輸入格式：

?

輸入文件rebuild.in的第一行包含兩個正整數(shù)N，M，表示了村莊的數(shù)目與公路的數(shù)量。

第二行包含N個非負(fù)整數(shù)t[0], t[1], …, t[N – 1]，表示了每個村莊重建完成的時間，數(shù)據(jù)保證了t[0] ≤ t[1] ≤ … ≤ t[N – 1]。

接下來M行，每行3個非負(fù)整數(shù)i, j, w，w為不超過10000的正整數(shù)，表示了有一條連接村莊i與村莊j的道路，長度為w，保證i≠j，且對于任意一對村莊只會存在一條道路。

接下來一行也就是M+3行包含一個正整數(shù)Q，表示Q個詢問。

接下來Q行，每行3個非負(fù)整數(shù)x, y, t，詢問在第t天，從村莊x到村莊y的最短路徑長度為多少，數(shù)據(jù)保證了t是不下降的。

?

輸出格式：

?

輸出文件rebuild.out包含Q行，對每一個詢問(x, y, t)輸出對應(yīng)的答案，即在第t天，從村莊x到村莊y的最短路徑長度為多少。如果在第t天無法找到從x村莊到y(tǒng)村莊的路徑，經(jīng)過若干個已重建完成的村莊，或者村莊x或村莊y在第t天仍未修復(fù)完成，則輸出-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%的數(shù)據(jù)，有N≤50；

對于30%的數(shù)據(jù)，有t[i] = 0，其中有20%的數(shù)據(jù)有t[i] = 0且N＞50；

對于50%的數(shù)據(jù)，有Q≤100；

對于100%的數(shù)據(jù)，有N≤200，M≤N*(N-1)/2，Q≤50000，所有輸入數(shù)據(jù)涉及整數(shù)均不超過100000。

---

?

以后不能小看floyd在n小時的應(yīng)用

floyd循環(huán)到k之前，求的是不經(jīng)過k的兩點之間最短路，正適合本題，連離線處理都省了，已經(jīng)有序

加一個t[n+1]=INF為了方便

注意滿足x和y修好了這個條件

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int N=205,INF=1e9+5; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,Q,d[N][N],t[N],a,b,w; int now,x,y; inline void re(){x=read()+1;y=read()+1;now=read();Q--;//printf("re %d %d %d\n",x-1,y-1,now); } int main(){n=read();m=read();for(int i=1;i<=n;i++) t[i]=read();for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) d[i][j]=d[j][i]=INF;for(int i=1;i<=m;i++){a=read()+1;b=read()+1;w=read();d[a][b]=d[b][a]=w;}Q=read();t[n+1]=INF;re();for(int k=1;k<=n+1;k++){while(now<t[k]){if(d[x][y]==INF||t[x]>now||t[y]>now) puts("-1");else printf("%d\n",d[x][y]);if(!Q) return 0;re();} for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/candy99/p/6057019.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P1119 灾后重建[Floyd]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。