洛谷 P1119 灾后重建 题解【floyd】【DP】

点击量：180

    floyd一开始思路想错了……还多加了一维？

目录

题目背景

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

 

题目描述

给出B地区的村庄数\(N\)，村庄编号从\(0\)到\(N-i\)，和所有\(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,\dots ,t_{N-1}\)，表示了每个村庄重建完成的时间，数据保证了\(t_0\le t_1\dots \le t_{N-1}\)。

 

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

 

接下来一行也就是\(M+3\)行包含一个正整数\(Q\)，表示\(Q\)个询问。

 

接下来\(Q\)行，每行\(3\)个非负整数\(x,y,t\)，询问在第\(t\)天，从村庄\(x\)到村庄\(y\)的最短路径长度为多少，数据保证了\(t\)是不下降的。

 

输出格式：

共\(Q\)行，对每一个询问\((x,y,t)\)输出对应的答案，即在第\(t\)天，从村庄\(x\)到村庄\(x\)的最短路径长度为多少。如果在第\(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\%\)的数据，有\(t_i=0\)，其中有\(20\%\)的数据有\(t_i=0\)且\(N>50\)；

对于\(50\%\)的数据，有\(Q\le 100\)；

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

题解：

    这个题完美地运用了floyd的DP思想。floyd的本质其实是三维DP，我们把被滚掉的一维还原回来，就成了\(f[k][i][j]\)表示\(i\)到\(j\)只经过编号不超过k的点的最短路（端点不受约束）。那么状态转移就变成了\(f[k][i][j]=\min (f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])\)。而这个题刚好就是只经过前一部分点的最短路。

    这个题比较轻松的一点就是，每个点的恢复时间是单调递增的，同时询问也是单调递增的。否则要把每个点按照恢复时间排序，询问也要变成离线了。

    于是我们可以用一个指针维护当前时间（时间是指询问的时间）已经被恢复的点的个数，然后把floyd的最外面一维拆开，每增加一个恢复的点就做一层floyd。每个询问都把当前时间可以恢复的点更新完，如果此时询问的答案仍然是\(\infty\)，或者两个端点任一个点还没有被恢复，那么输出-1。其他情况就可以直接输出答案。

    注意这个题的编号从0开始。

Code：

#include<cstdio>
#include<cstring>
int f[222][222];
int t[222];
int main()
{
    memset(f,0x3f,sizeof(f));
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)
    {
        scanf("%d",&t[i]);
        f[i][i]=0;
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        f[u][v]=w;
        f[v][u]=w;
    }
    int q,tt=0;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d%d",&u,&v,&w);
        while(t[tt]<=w&&tt<n)//把能恢复的都恢复
        {
            for(int i=0;i<n;++i)
                for(int j=0;j<n;++j)
                    f[i][j]=f[i][j]<f[i][tt]+f[tt][j]?f[i][j]:f[i][tt]+f[tt][j];
            ++tt;
        }
        if(u>=tt||v>=tt||f[u][v]==0x3f3f3f3f)
        {
            puts("-1");
            continue;
        }
        printf("%d\n",f[u][v]);
    }
    return 0;
}