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

作者: wjyyy 分类: DP,floyd,解题报告 发布时间: 2018-09-09 21:37

点击量:17

 

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

 

题目背景

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

 

题目描述

给出B地区的村庄数\(N\),村庄编号从\(0\)到\(N-i\),和所有\(M\)条公路的长度,公路是双向的。并给出第\(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;
}

说点什么

avatar
  Subscribe  
提醒
/* */