P1119 灾后重建(Floyd)

蔚落 2023-06-22 06:25 22阅读 0赞

#### 题目来源 ####

[P1119 灾后重建][P1119]

--------------------

#### 解题思路 ####

*  本题可用dijkstra做，对于每个时间限制都输入dijkstra进行判断，但时间复杂度高，需要剪枝、O2优化等操作才能勉强通过，不是本题正解
 *  本题最大结点数为200符合floyd算法的计算范围
 *  **输入每个村庄重建完成的时间，保证是不下降的，且每次询问的时间也是不下降的**
 *  **则可以对现在的k输入进floyd进行对每两个结点间距离的更新(即以这个点作为中间点，对两点之间的最短距离进行更新，符合floyd算法内涵)**
 *  注意路是双向的，赋值时需要对两个赋值
 *  自己到自己结点的距离要初始化为0

--------------------

#### 代码实现 ####

//floyd正解
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1000;
    const int INF = 0x3f3f3f3f;
    
    int t[MAXN];
    int N, M, Q;
    int d[MAXN][MAXN];
    
    void floyd(int k)
    { 
        for(int i = 0; i < N; i++)
        { 
            for(int j = 0; j < N; j++)
            { 
                if(d[i][k] != INF && d[k][j] != INF && d[i][k]+d[k][j] < d[i][j])
                { 
                    d[j][i] = d[i][j] = d[i][k]+d[k][j];  //双向边更新
                }
            }
        }
    }
    int main()
    { 
        fill(d[0], d[0]+MAXN*MAXN, INF);
    // freopen("in.txt","r",stdin);
        scanf("%d%d",&N,&M);
        for(int i = 0; i < N; i++)
        { 
            scanf("%d",&t[i]);
            d[i][i] = 0;      //初始化
        }
        for(int i = 0; i < M; i++)
        { 
            int u, v, w;
            scanf("%d%d%d",&u,&v,&w);
            d[u][v] = d[v][u] = w;
        }
        scanf("%d",&Q);
        int now = 0;         //当前作为更新的点
        for(int i = 0; i < Q; i++)
        { 
            int x, y, t0;
            scanf("%d%d%d",&x,&y,&t0);
            for( ; t[now] <= t0 && now < N; now++) //更新
            { 
                floyd(now);
            }
            if(t[x]>t0 || t[y]>t0 || d[x][y] == INF)
                printf("-1\n");
            else
                printf("%d\n",d[x][y]);
        }
        return 0;
    }

[P1119]: https://www.luogu.com.cn/problem/P1119