【題目描述】

B地區(qū)在地震過后，所有村莊都造成了一定的損毀，而這場地震卻沒對(duì)公路造成什么影響。但是在村莊重建好之前，所有與未重建完成的村莊的公路均無法通車。換句話說，只有連接著兩個(gè)重建完成的村莊的公路才能通車，只能到達(dá)重建完成的村莊。
　　給出B地區(qū)的村莊數(shù)N，村莊編號(hào)從0到N-1，和所有M條公路的長度，公路是雙向的。并給出第i個(gè)村莊重建完成的時(shí)間t[i]，你可以認(rèn)為是同時(shí)開始重建并在第t[i]天重建完成，并且在當(dāng)天即可通車。若t[i]為0則說明地震未對(duì)此地區(qū)造成損壞，一開始就可以通車。之后有Q個(gè)詢問(x, y, t)，對(duì)于每個(gè)詢問你要回答在第t天，從村莊x到村莊y的最短路徑長度為多少。如果無法找到從x村莊到y(tǒng)村莊的路徑，經(jīng)過若干個(gè)已重建完成的村莊，或者村莊x或村莊y在第t天仍未重建完成 ，則需要返回-1。

輸入輸出格式

輸入格式：

輸入文件rebuild.in的第一行包含兩個(gè)正整數(shù)N，M，表示了村莊的數(shù)目與公路的長度。
　　第二行包含N個(gè)非負(fù)整數(shù)t[0], t[1], …, t[N – 1]，表示了每個(gè)村莊重建完成的時(shí)間，數(shù)據(jù)保證了t[0] ≤ t[1] ≤ … ≤ t[N – 1]。
　　接下來M行，每行3個(gè)非負(fù)整數(shù)i, j, w，w為不超過10000的正整數(shù)，表示了有一條連接村莊i與村莊j的道路，長度為w，保證i≠j，且對(duì)于任意一對(duì)村莊只會(huì)存在一條道路。
　　接下來一行也就是M+3行包含一個(gè)正整數(shù)Q，表示Q個(gè)詢問。
　　接下來Q行，每行3個(gè)非負(fù)整數(shù)x, y, t，詢問在第t天，從村莊x到村莊y的最短路徑長度為多少，數(shù)據(jù)保證了t是不下降的。

輸出格式：

輸出文件rebuild.out包含Q行，對(duì)每一個(gè)詢問(x, y, t)輸出對(duì)應(yīng)的答案，即在第t天，從村莊x到村莊y的最短路徑長度為多少。如果在第t天無法找到從x村莊到y(tǒng)村莊的路徑，經(jīng)過若干個(gè)已重建完成的村莊，或者村莊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

思路

這個(gè)其實(shí)是個(gè)最短路問題，用的是Floyd算法，不過要在Floyd的過程中加入一些東東
我們floyd的3層循環(huán)如下：

for (int k=1;k<= n;k++) for (int i = 1;i <= n;i++) for (int j=1;j <= n;j++) w[i][j]=min(w[i][j],w[i][k]+w[k][j]);

這里的k層循環(huán)(第一層)枚舉的是經(jīng)過哪一些點(diǎn)作為中間點(diǎn)來縮短i->j的距離。 可以理解為用了前k個(gè)點(diǎn)作為中間點(diǎn)來嘗試更新任意兩點(diǎn)之間的距離。，這點(diǎn)可以為我們所利用。
看一下我們的詢問：x,y,time 如果t[x] 或者t[y]>time則肯定是輸出-1的。 對(duì)于其他的 我們可以在k層循環(huán)中的i,j循環(huán)完畢之后加上下面這些東西。
即 ：
for (k=1->n) { for (i=1->n) for (j =1->n) … 在這個(gè)位置加上我們下面所說的東西； }
k層循環(huán)仍是枚舉n個(gè)點(diǎn)。 如果t[k]<=a[now].time且t[k+1] <=a[now].time 則k可以繼續(xù)枚舉。表示我們可以利用k和k+1來作為中間點(diǎn)更新任意兩點(diǎn)之間的距離。 如果遇到t[k]<=a[now].time且t[k+1]>a[now].time。 則表示我們最多只能用k來作為中間點(diǎn)更新任意兩點(diǎn)之間的距離了。 這時(shí)我們只能嘗試在利用前k個(gè)點(diǎn)之后輸出w[x][y]了。 不能再用k+1這個(gè)點(diǎn)了。因?yàn)閗+1這個(gè)點(diǎn)在a[now].time時(shí)還沒有修建好。
遇到這樣的k之后。now++.(a[now].time是隨著now的增加遞增的)。
如果now遞增后t[k+1]<=a[now].time了。則可以繼續(xù)利用k+1來作為中間點(diǎn)更新任意兩點(diǎn)之間的距離。
然后我們把k層循環(huán)的下界改為0. 因?yàn)榭赡苡性?時(shí)刻的詢問

大概就是這樣啦，大家可以看看代碼

AC代碼

#include <cstdio>
#include <cstring>struct question //用結(jié)構(gòu)體把詢問存下來。
{int x, y, time;
};int n, m, t[201] = { 0 }, w[201][201], q; //t數(shù)組是各個(gè)節(jié)點(diǎn)修建好的時(shí)間。
question a[50001] = { 0 };void input_data()
{memset(w, 127 / 3, sizeof(w));//一開始w數(shù)組賦值為一個(gè)很大的數(shù)字。scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) //輸入各個(gè)節(jié)點(diǎn)修建好的時(shí)刻。scanf("%d", &t[i]);for (int i = 1; i <= m; i++) //輸入邊權(quán)信息。{int x, y, z;scanf("%d%d%d", &x, &y, &z);x++; y++;w[x][y] = w[y][x] = z;}scanf("%d", &q);for (int i = 1; i <= q; i++) //輸入q個(gè)詢問。{scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].time);a[i].x++;a[i].y++;}
}void get_ans()
{int now = 1;t[n + 1] = t[n] + 10000; //這是防止上溢。for (int k = 0; k <= n; k++) //k從0開始枚舉{for (int i = 1; i <= n; i++) //以k作為中間節(jié)點(diǎn)嘗試更新任意兩點(diǎn)之間的距離。for (int j = 1; j <= n; j++)if (w[i][j] > w[i][k] + w[k][j])w[i][j] = w[i][k] + w[k][j];while (now <= q && t[k] <= a[now].time && t[k + 1] > a[now].time){//如果詢問還沒結(jié)束。且這個(gè)節(jié)點(diǎn)在所詢問的時(shí)間內(nèi)。且k+1這個(gè)節(jié)點(diǎn)修建的時(shí)間超過詢問的時(shí)間if (t[a[now].x] > a[now].time || t[a[now].y] > a[now].time)printf("-1\n");else //輸出依靠前k個(gè)節(jié)點(diǎn)作為中間節(jié)點(diǎn)更新出的任意兩點(diǎn)之間的距離{if (w[a[now].x][a[now].y] >= w[0][0])printf("-1\n");elseprintf("%d\n", w[a[now].x][a[now].y]);}now++; //看一下下一個(gè)詢問是否符合要求。}if (now > q) //如果詢問都輸出了則結(jié)束。break;}
}int main()
{input_data();get_ans();return 0;
}

別忘了點(diǎn)贊哦( * ^ ▽ ^ * )