洛谷P1119 灾后重建 图论 脑洞题

洛谷P1119 灾后重建

图论   脑洞题   floyd   
floyd中 k 的意义 通过前 k 个点 作为中间的节点 更新 i 到 j 的最短路 也就是 只经过前 k 个点 的最短路

帮助理解Floyd算法的好题！初学Floyd算法时，相信很多人和我一样，只是把几行代码背下来，
并没有了解Floyd算法到底是什么原理。以下介绍Floyd算法的原理：

Floyd算法的本质是动态规划，其转移方程为：f(k,i,j) = min( f(k-1,i,j), f(k-1,i,k)+f(k-1,k,j) )。

f(k,i,j)表示路径除开起点i与终点j，只经过前k个点中的某些点，从i到j的最小值。计算这个值只需要考虑两种情况：
最短路经过k，和最短路不经过k（那么就经过前k-1个点中的某些点）。由于k要从k-1转移而来，自然k为最外层的循环。
而经过状态压缩（类似于背包问题）后，就变成了我们熟悉的f(i,j) = min( f(i,j), f(i,k)+f(k,j) )了。

本题同理，只是k表示的是最先修好的前k个村庄。不过由于出题人非常良心地帮我们把修理时间和询问时间都排序了，
所以就没什么关系了- -用Floyd枚举k时，枚举到下一个询问的时间点就停止。回答询问之后，再继续枚举。

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std ; 

const int maxn = 211,maxq = 50011,inf = 1e9 ; 
int n,m,Q,now ; 
int e[maxn][maxn],t[maxn] ; 
int tq[maxq],qs[maxq],qt[maxq] ; 

inline int read() 
{
    char ch = getchar() ; 
    int x = 0 , f = 1 ; 
    while(ch<'0'||ch>'9') { if( ch=='-' ) f = -1 ; ch = getchar() ; } 
    while(ch>='0'&&ch<='9') { x = x*10 + ch - 48 ; ch = getchar() ; } 
    return x * f ; 
}

inline int print(int now) 
{
    if( t[ qs[now] ] > tq[ now ] || t[ qt[now] ] > tq[ now ] ) 
        return -1 ; 
    if( e[qs[now]][qt[now]]==inf ) 
        return -1 ; 
    return e[qs[now]][qt[now]] ;  
}

int main() 
{
    n = read() ; m = read() ; 
    for(int i=0;i<n;i++) t[ i ] = read() ; 
    for(int i=0;i<n;i++) 
        for(int j=0;j<n;j++) e[ i ][ j ] = inf ; 
        
    
    int x,y,v ; 
    for(int i=1;i<=m;i++) 
    {
        x = read() ; y = read() ; v = read() ; 
        e[ x ][ y ] = v ; e[ y ][ x ] = v ; 
    }
    
    Q = read() ;  
    for(int i=1;i<=Q;i++) 
    {
        qs[ i ] = read() ; qt[ i ] = read() ; tq[ i ] = read() ;   
    }
    
    now = 1 ; 
    for(int k=0;k<n;k++) 
    {
        while( now <= Q && tq[now] < t[ k ] )    // 这样相当于做询问 Q 是 就已经将 在他之前的 边考虑到
                                                //询问的时间小于当前时间则输出 
        {
            printf("%d
",print( now ) ) ; 
            now++ ; 
        }
        for(int i=0;i<n;i++) 
            for(int j=0;j<n;j++) 
                e[ i ][ j ] = min(e[ i ][ j ],e[ i ][ k ] + e[ k ][ j ]) ; 
    }
    
    while( now<=Q ) 
    {
        printf("%d
",print(now)) ; 
        now++ ; 
    }
     
    return 0 ; 
}