P1119 灾后重建

题目背景

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述

给出 B 该地区的村庄数量N，村庄编号从0到N-1，和所有M公路长度为双向。并给出第i村庄重建完成的时间ti，你可以认为它是同时重建的ti天重建完成，当天即可通车。若ti为0说明地震没有损坏这个地区，一开始就可以通车。之后有Q个询问(x,y,t)，你必须回答每一个问题。t天，从村庄x到村庄y最短路径长度是多少？若找不到从x村庄到y村庄的路径经过几个重建的村庄或村庄x或村庄y在第t天还没有重建，需要返回-1。

输入格式

第一行包括两个正整数N,M，表示村庄和公路的数量。

第二行包含NN个非负整数t0,t1,…,tN?1.表示每个村庄重建的时间，数据得到保证t0≤t1≤…≤tN?1。

接下来M行，每行3个非负整数i, j, w，w正整数不超过1万，说明有一条连接村i和村j的路，长度为w，保证i≠j，任何一对村庄只有一条路。

下一行就是M 三行包含正整数Q，表示Q个询问。

接下来Q行，每行3个非负整数x, y, t问问第一天，从村x到村y的最短路径长度是多少，数据保证t不会下降。

输出格式

共Q行，每个问题(x, y, t)输出相应的答案，即第二天，从村x到村y的最短路径长度是多少。如果在第二天找不到从x村到y村的路径，在几个已经重建的村庄之后，或者在第二天没有修复村x或村y，则输出-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%的数据，有N≤50；

对于30%的数据，有ti=0，其中有 %的数据有ti=0且N>50；

对于50%的数据，有Q≤100；

对于100%的数据，有N≤200N≤200，M≤N×(N?1)/2，Q≤50000，所有输入数据涉及整数均不超过100000。

这是一道用Floyd算法解释最短路练习

在解决这个问题之前，让我们先了解一下floyd算法，这是一个看似简单的算法，其本质是动态规划的思想，三重循环 判断可以在图中任何两点之间找到最短的路径

该算法的主要思路是通过其他中转点找到两点之间的最短距离。我们知道两点之间有多条路径。如果另一条路可以缩短距离，则更新最短距离，其基本思想是使用其他点进行中转，以达到最短路的目的。

两点之间可以有一个中转点，也可以有多个中转点更新最短距离

void floyd() {  for (int k = 0; k < N; k  ) {   for (int i = 0; i < N; i  ) {    for (int j = 0; j < N; j  ) {     g[i][j] = min(g[i][j], g[i][k]   g[k][j]);    }   }  } }

核心思想:一开始只允许0号顶点中转，下一步只允许1~2号顶点中转...允许1~N从i号顶点到j号顶点的最短的最短距离，即从i号顶点到j号顶点的最短距离。

让我们回头看问题的意思：

给出所有的边，按照时间顺序更新每一个可用的点（即修建好的村庄）对于每个时间点进行两点之间询问，求目前建设的所有村庄来说任何两点之间的最短路

所以这个问题就是让我们用它floyd算法解释最短路径

AC代码

#define _CRT_SECURE_NO_WARNINGS #include  using namespace std;  const int INF = 0x3f3f3f; const int MAXN = 200; int N, M, Q;//公路数量，Q个询问 int g[MAXN][MAXN];//邻接矩阵 int arr[MAXN];////完成每个村庄重建的时间  void floyd(int k) {  for (int i = 0; i < N; i  ) {   for (int j = 0; j < N; j  ) {    g[i][j] = min(g[i][j], g[i][k]   g[k][j]);   }  } }  int main() {  ios::sync_with_stdio(false);//关闭同步锁  cin.tie(nullptr);  cout.tie(nullptr);   cin >> N >> M;  for (int i = 0; i < N; i  ) {   cin >> arr[i];////输入每个村庄建庄所需的时间  }  for (int i = 0; i < N; i  ) {   for (int j = 0; j < N; j  ) {    if (i != j)     g[i][j] = INF;///初始化为最大值    else     g[i][j] = 0;   }  }  while (M--)  {   int i, j, w;   cin >> i >> j >> w;   g[i][j] = g[j][i] = w;  }  cin >> Q;  int k = 0;  while (Q--)  {   int x, y, t;   cin >> x >> y >> t;   //如果现在更新点的时间在询问点之前   while (arr[k] <= t && k < N) {    floyd(k);    k  ;   }   ///村x或村y第二天还没有重建   if (arr[x] > t || arr[y] > t) {    cout << -1 << endl;   }   else {    if (g[x][y] == INF)     cout << -1 << endl;    else     cout << g[x][y] << endl;;   }  }  return 0; }