【洛谷 P1119】灾后重建【Floyed最短路】_综合

题目背景

题目
$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

输出 #1

-1
-1
5
4

分析：

根据题意：
时间顺序更新两点之间的可用点 提出询问后更新最短路
这样说其实就是 $floyed$ 的思想，前 $k$ 个点更新最短路( $spfa$ 已死 $floyed$ 永远滴神！！)
数据只有 $200$ 邻接矩阵存储边 然后处理询问并调用 $floyed$ 即可……
关于处理询问部分：

	int qwq;scanf("%d",&qwq);int p=0;  //记录当前村庄编号for(int i=1;i<=qwq;i++){scanf("%d%d%d",&u,&v,&w);while(a[p]<=w&&p<n)  //当前更新点时间在询问前{floyed(p);p++;  //处理之前的村庄}if(a[u]>w||a[v]>w) printf("-1\n");  //未建成else{if(f[u][v]==inf) printf("-1\n");  //未联通elseprintf("%d\n",f[u][v]);} }

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 1e9
#pragma GCC optimize(2)
using namespace std;
int n,m,a[205],f[205][205];
void floyed(int k)  //永远滴神求最短路
{for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(f[i][j]>f[i][k]+f[k][j])f[i][j]=f[j][i]=f[i][k]+f[k][j];
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&a[i]);for(int i=0;i<n;i++)for(int j=0;j<n;j++)f[i][j]=inf;  //初始化for(int i=0;i<n;i++)f[i][i]=0;int u,v,w;for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w);f[u][v]=w;f[v][u]=w;  //邻接矩阵存储边} int qwq;scanf("%d",&qwq);int p=0;for(int i=1;i<=qwq;i++)  //询问部分{scanf("%d%d%d",&u,&v,&w);while(a[p]<=w&&p<n)  {floyed(p);p++;}  //处理之前的村庄if(a[u]>w||a[v]>w) printf("-1\n");  //未建成else{if(f[u][v]==inf) printf("-1\n");   //未连边elseprintf("%d\n",f[u][v]);} }return 0;
}