【题解】P1119 灾后重建

题目地址

理解Floyed的本质

　　Floyed的本质是动态规划。

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

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

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

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

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

　　　　输出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  ;

}

Thanks！