「题解」灾后重建

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是不下降的。

---

二 题解

简化题意，就是给定一张无向图，并且节点$i$在时间$t_i$时才可用，求任意时间两个节点间的最短路（不连通输出-1）。

“任意点间最短路”，是不是有点钦点floyd的意味？

看floyd的转移方式。
设$f_{i,j,k}$表示仅考虑经过前$k$个点中转，点$i$到$j$的最短路。

$f_{i,j,k}$可以继承前面的状态（$f_{i,j,k-1}$），也可以尝试用新增的节点$k$来中转，那么转移方程：
$$ f_{i,j,k} = \min f_{i,j,k-1},f_{i,k,k-1}+f_{k,j,k-1} |(i,k) \in E,(k,j) \in E $$

状态$f_{i,j}$的转移来自同一个层级（都是$k-1$），那么$k$这一维可以滚动（不过$k$一定在最外重循环）。转移方程变成：
$$ f_{i,j} = \min f_{i,j},f_{i,k}+f_{k,j} |(i,k) \in E,(k,j) \in E $$

那么也就是说：随着$k$的变化，所经过的中转节点不断增加，从而使得最短路不断松弛。
而本题就是要控制最短路经过的中转节点，在仅经过一些节点的情况下求出最短路。

也就有了下面的想法：
把村庄按修建时间升序排序，以该顺序作为$k$这一维循环的顺序，来更新最短路。这样就能控制在某一时刻内，仅有$t_i \leqslant t_k$的村庄$i$可以参与中转最短路。
然后离线处理询问。把每个询问按照询问时间升序排序，若当前前$k$个村庄更新后可以回答（排序后的）第一个问题（$t_k \geqslant t_q$，$t_q$是询问的时间），那么就记录答案，并删掉这个问题。
不考虑排序消耗的时间，复杂度大约是$O(n^3+q)$。

但是出题人很良心：数据是排好序的（题目中加粗了）。那么直接排，然后顺序处理询问就好了。

注意点的编号是$0 \text{~} n-1$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdio>
using namespace std;

int read(){
    int s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

const int CN=220;

const int INF=0x3f3f3f2f;

//v define
int f[CN][CN],k=1,n,m,q;
int bt[CN];

void init(){
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++) f[i][i]=0;
}

int main()
{
    n=read(); m=read();
    init();
    for(int i=1;i<=n;i++)
        bt[i] = read();
    while(m--){
        int x=read(),y=read(),z=read();
        x+=1; y+=1; //把编号变成1 ~ n
        f[x][y] = f[y][x] = z;
    }
    
    q=read();
    while(q--)
    {
        int x=read(),y=read(),t=read();
        x+=1; y+=1;
        
        if(bt[x]>t || bt[y]>t){
            printf("-1\n");
            continue;
        }
        
        while(bt[k]<=t && k<=n){ //分段更新，每次一直更新到当前时间 = 询问时间
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
            k++;
        }
        
        if(f[x][y] > INF) printf("-1");
            else printf("%d",f[x][y]);
        printf("\n");
    }
    
    return 0;
}