【题解】P1119 灾后重建

题目地址

理解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 = 0 ;
    char C = GC ;
    while (C > '9' || C < '0') C = GC ;
    while (C >='0' && C <='9') {
        X = X * 10 + C - '0' ;
        C = GC ;
    }
    return X ;
}
const int Maxn = 201 ,INF = 20021020 * 4 ;
int N , M , T[Maxn] ,A[Maxn][Maxn] ;
int main () {
    freopen ("P1119.in" , "r" , stdin) ;
    N = Qread() , M = Qread () ;
    for (re int i = 0 ; i < N ; ++ i) T[i] = Qread () ;
    Clean(A , 0x3f) ;
    for (re int i = 1 ; i <= M ; ++ i) {
        int X = Qread () , Y = Qread() , L = Qread() ;
        A[X][Y] = A[Y][X] = L ;
    }
    int Q = Qread() ,K = 0 ;
    for (re int I = 1 ; I <= Q ; ++ I ) {
        int From = Qread () , Goto = Qread() , Time = Qread() ;
        for (; T[K] <= Time && K < N; ++ K) for (re int i = 0 ; i < N; ++ i) for (re int j = 0; 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
") ;
        else printf ("%d
" , A[From][Goto]) ;
    }
    fclose (stdin) ,fclose (stdout);
    return 0 ;
}

 Thanks！