题意描述：

B地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。

但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。

换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

现在，给出地区的村庄数，村庄编号从到，和条公路的长度。

公路是双向的。并给出第个村庄重建完成的时间

若为则说明地震未对此地区造成损坏，一开始就可以通车。

之后有个询问

对于每个询问你要回答在第天，从村庄到村庄的最短路径长度为多少。

如果无法找到从村庄到村庄的路径，或者村庄或村庄在第天仍未重建完成 ，则输出。

输入格式：

第一行包含两个正整数 , ，表示了村庄的数目与公路的数量。

第二行包含个非负整数表示了每个村庄重建完成的时间.

接下来行，每行个非负整数,表示了有一条连接村庄与村庄的道路

接下来一行包含一个正整数，表示个询问。

接下来行，每行个非负整数询问在第天，从村庄到村庄的最短路径长度为多少.

输出格式：

共行，对每一个询问输出对应的答案。

如果在第天无法找到从村庄到村庄的路径，或者村庄或村庄在第天仍未修复完成，则输出。

Input & Output 's examples

Input 's eg

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

Output 's eg

-1
-1
5
4

数据范围和约定

对于的数据，有；

对于另外的数据，

对于的数据，有

对于的数据，有，，所有输入数据均为型整数且均不超过。

分析

一道好题

彻底刷新了我对的看法。

首先，我们认真读一遍题目，不难发现以下几点

1. 的取值范围极小，只有200.（疯狂暗示

2. 不下降（即是按时间顺序从小到大给出的）

3. 本题可以在线求解

4. 村庄标号从0开始（坑了我一次提交机会）

现在我们一起看一下算法的主要思想。

算法基于DP，说白了，就是用最外层循环不停的枚举每两个点之间的中间点来进行松弛操作。

而在本题中，每一个村庄是否可以作为中间点取决于它是否重建完成。也就是说，在村庄重建完成之前，它不可以作为中间点进行枚举

所以我们只需要将最外层用来枚举中间点的循环加一个特判，判断该点能否被用来中转即可。

但要注意，如果起点或终点没有完成重建，需要输出-1

因此，我们还需要进行一次特判，用于判断起点与重点是否重建完成。

一个 + 两个特判 = 一道蓝题

是不是很简单啊（逃）~

附件（AC标程，防作弊已开启）

#include<iostream>
#define N 201 

using namespace std;

int n , m;
int a[N];
int l , r , w;
int f[N][N];    //由于本题数据范围较小，作者采用邻接矩阵存图 
int q;
int x , y , t;

void floyd(int k){        //Floyd主体函数 
    for(int i = 0; i <= n - 1; i ++){
        for(int j = 0; j <= n - 1; j ++){
            f[i][j] = min(f[i][j] , f[i][k] + f[k][j]); 
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i <= n - 1; i ++){
        cin >> a[i];
    }
    for(int i = 0; i <= n - 1; i ++){
        for(int j = 0; j <= n - 1; j ++){
            f[i][j] = 1e9;        //初始化邻接矩阵 
        }
    }
    for(int i = 0; i <= n - 1; i ++){
        f[i][i] = 0;
    }
    for(int i = 0; i <= m - 1; i ++){
        cin >> l >> r >> w;
        f[l][r] = w;        //由于是双向道路，所以需要建两次边 
        f[r][l] = w;
    }
    cin >> q;
    int now = 0;    //now代表今天是第几天，用于枚举天数 
    for(int i = 0; i <= q - 1; i ++){
        cin >> x >> y >> t;
        if(a[x] > t || a[y] > t){    //特判，如果起点或终点就没有重建，直接跳过循环 
            cout << "-1" <<endl;
            continue;
        }
        while(a[now] <= t && now < n){
            floyd(now);
            now ++;
        }
        if(f[x][y] == 1e9){        //如果没有联通路，输出-1 
            cout << "-1" <<endl;
        }
        else{ 
            cout << f[x][y] << endl;
        }
    }
    return 0;
}
//Written By Payphone-X 

THE END