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，表示了村庄的数目与公路的数量。

第二行包含 N 个非负整数 t0​,t1​,⋯,tN−1​，表示了每个村庄重建完成的时间，数据保证了 t0​≤t1​≤⋯≤tN−1​。

接下来 M 行，每行 3 个非负整数 i,j,w，w 为不超过 10000 的正整数，表示了有一条连接村庄 i 与村庄 j 的道路，长度为 w，保证 j≠i，且对于任意一对村庄只会存在一条道路。

接下来一行也就是 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复制

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，其中有 20% 的数据有 ti​=0 且 N>50；
• 对于 50% 的数据，有 Q≤100；
• 对于 100% 的数据，有 1≤N≤200，20≤M≤2N×(N−1)​，1≤Q≤50000，所有输入数据涉及整数均不超过 105。

解析：

这题一看就是图论的问题，阅读完题目后村庄的修建时间是不减递增的。后面的询问时间也是递增的。

在联想到最短路问题有Floyd算法可以很快的求出最短路径，其数据也没有那么大。

这是一道不错的Floyd算法的运用。

普通的Floyd算法是三层for循环，dp[i][j] = min(dp[i][k],dp[k][j],dp[i][j]);

for(k=1;k<=n;k++)

    for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

            if(e[i][j]>e[i][k]+e[k][j])

                 e[i][j]=e[i][k]+e[k][j];

从i地点到k,在从k到达j。

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

不正好就是Floyd算法中使用前k个节点更新最短路的思维吗？

核心代码：

inline void updata(int k){ //以k为中心的点进行更新
    for(int i = 0;i <n;i++){
        for(int j = 0;j < n;j++){
            if(f[i][j] > f[i][k] + f[j][k])
            {
                f[i][j] = f[j][i] = f[i][k] + f[k][j];
            }
        }
    }
    return;
}

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 205
#define endl '\n'
int n,m;
int a[N];
int f[N][N];
inline void updata(int k){
    for(int i = 0;i <n;i++){
        for(int j = 0;j < n;j++){
            if(f[i][j] > f[i][k] + f[j][k])
            {
                f[i][j] = f[j][i] = f[i][k] + f[k][j];
            }
        }
    }
    return;
}
int main()
{
    cin >>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] = 1e9;
        }
    }
    for(int i = 0;i < n;i++) 
    {
        f[i][i] = 0;
    }
    int s1,s2,s3;
    for(int i = 1;i <= m;i++){ //从s1 - s2 的距离 
        scanf("%d%d%d",&s1,&s2,&s3);
        f[s1][s2] = f[s2][s1] = s3;
    }
    int q;
    cin >> q;
    int now = 0;
    for(int i = 1;i <= q;i++){
        scanf("%d%d%d",&s1,&s2,&s3);
        while(a[now] <= s3 && now <  n){ //now是指遍历到那个节点 
            updata(now);
            now++;
        }
        if(a[s1] > s3||a[s2] > s3) cout << -1<<endl;
        else{
            if(f[s1][s2] ==1e9) cout << -1 <<endl;
            else cout <<f[s1][s2] <<endl;
        }
    }
    return 0;
}
//4 5
//1 3 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