首页技术正文

【题解】P1119 灾后重建

程序员士魁技术 2022年11月18日

0 收藏 423 点赞 2,225 浏览 1020 个字

题目地址

理解Floyed的本质

　　Floyed的本质是动态规划。

　　在地K次循环中，Floyed算法枚举任意点对(X,Y)，在这之前，K从未做过任何点对的中点。因此，可以利用K为中转的路径长度更新。

　　在1..K的循环中，F[i][j]被更新为只允许借助前K个点为中转，点i和点j之间的最短路。

　　题目保证了单调性，这样就很好办了，无须排序

　　从1-Q依次处理每个询问：

　　　　对于任意的点X∈[T_Q-1,T_Q]，利用他们更新其他点

　　　　输出A[From][Goto]作为答案

Code

#include <cstdio>
#include <cstring>
#define re register
#define GC getchar()
#define Min(X,Y) (X<Y?X:Y)
#define Clean(X,K) memset(X,K,sizeof(X))
int Qread () {
    int X =  ;
    char C = GC ;
    while (C > '' || C < '') C = GC ;
    while (C >='' && C <='') {
        X = X *  + C - '' ;
        C = GC ;
    }
    return X ;
}
const int Maxn =  ,INF =  *  ;
int N , M , T[Maxn] ,A[Maxn][Maxn] ;
int main () {
    freopen ("P1119.in" , "r" , stdin) ;
    N = Qread() , M = Qread () ;
    for (re int i =  ; i < N ; ++ i) T[i] = Qread () ;
    Clean(A , 0x3f) ;
    for (re int i =  ; i <= M ; ++ i) {
        int X = Qread () , Y = Qread() , L = Qread() ;
        A[X][Y] = A[Y][X] = L ;
    }
    int Q = Qread() ,K =  ;
    for (re int I =  ; I <= Q ; ++ I ) {
        int From = Qread () , Goto = Qread() , Time = Qread() ;
        for (; T[K] <= Time && K < N; ++ K) for (re int i =  ; i < N; ++ i) for (re int j = ; j < N; ++ j) A[i][j] = Min (A[i][j] , A[i][K] + A[K][j]) ;
        if (A[From ][Goto ] > INF || Time < T[From] || Time < T[Goto] ) printf ("-1\n") ;
        else printf ("%d\n" , A[From][Goto]) ;
    }
    fclose (stdin) ,fclose (stdout);
    return  ;
}