美文网首页
洛谷 P1119 灾后重建 题解

洛谷 P1119 灾后重建 题解

作者: 帅气的小屁孩_8d50 | 来源:发表于2018-10-31 23:16 被阅读0次

题目大意

给你n个点建立的时间,然后给你m条边,之后有q个询问,每次询问在某一天图中两个点之间的最短距离。

题目链接

Luogu P1119

思路

这个题目中有两个很关键的地方,首先我们可以看到题目中给出每个点建立的时间(即村子修复的时间是递增的)然后询问中的天数也是递增的。所以这样就大大减少了编程难度。因为我们要求任意两点之间的最短路再加上题目中点的个数那么小,所以我们可以想到要用Floyd算法。再Floyd算法中我们的那三层循环中最外层循环枚举的那个点的作用相当于在图中假如这个点,然后再用这个点去优化途中任意两点间的距离。这与这个题目中点的建立在本质上是一样的,所以我们枚举到k号点相当与在图中建立这个点。
假设我们现在枚举到k号点,说明k号点在图上建立了起来。那么询问中询问时间在[t[k],t[k + 1])之内的询问都可以回答。然后我们按照题意回答询问即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e2 + 5;
const int M = 2e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m, q;
int u, v, w;
int time_tmp; //要查询的时间
int t[N]; //每个村庄修复的时间
int matrix[N][N];

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

void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline int Min(int x, int y) {
    return x <= y ? x : y;
}

int main(int argc, char const *argv[]) {
    memset(matrix, 0x3f, sizeof(matrix));
    n = read(), m = read();
    for (register int i = 0; i < n; ++i) {
        t[i] = read();
        matrix[i][i] = 0;
    }
    for (register int i = 0; i < m; ++i) {
        u = read(), v = read(), w = read();
        matrix[u][v] = Min(matrix[u][v], w);
        matrix[v][u] = Min(matrix[v][u], w);
    }
    q = read();
    int pos_start = 0; //从第0个村庄开始修复
    for (register int i = 0; i < q; ++i) {
        u = read(), v = read(), time_tmp = read();
        int pos = pos_start;
        while (pos < n && t[pos] <= time_tmp) //直到修复到可以查询为止 
            ++pos;
        for (register int k = pos_start; k < pos; ++k) {
            for (register int i = 0; i < n; ++i) {
                for (register int j = 0; j < n; ++j) {
                    if (matrix[i][j] > matrix[i][k] + matrix[k][j])
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                }
            }
        }
        if (t[u] > time_tmp || t[v] > time_tmp || matrix[u][v] == INF) {
            printf("-1\n");
        } else {
            printf("%d\n", matrix[u][v]);
        }
        pos_start = pos;
    }
    return 0;
}

相关文章

  • 洛谷 P1119 灾后重建 题解

    题目大意 给你个点建立的时间,然后给你条边,之后有个询问,每次询问在某一天图中两个点之间的最短距离。 题目链接 L...

  • 灾后重建???

    疫情犹如蝗虫过境,寸草难生,片甲难留。 虽然前期便已经有了未来很难的意识,但是真正开始发生在身边时,才更有体会。 ...

  • 灾后重建

    熬了四十多个小时,去一线帮忙抢险救援的老公终于回来了,四十多个小时,没有合眼,都不知道他是什么意志强撑着开了四...

  • 灾后重建1114

    美妙的感受没有超过2小时,我就再度陷入崩溃 按照长飞老师的练习建议,回家我就给了老公一个五分钟的温暖抱抱,果真非常...

  • BCP手册-业务特持续性计划

    BCP手册,解决企业在疫情等灾难后的重建 主要解决两个问题: ①灾难发生时怎么做? ②灾后重建怎么做? 重点在于后...

  • 洛谷P1025题解

    题目链接:洛谷P1025 题目描述 将整数分成份,且每份不能为空,任意两个方案不相同(不考虑顺序)。 例如:,下面...

  • 洛谷P1002题解

    少儿编程咨询、算法咨询请加微信307591841或QQ群581357582诺依曼算法公众号.jpg

  • 厂房灾后重建基本完工

    2018年12月30日凌晨,多年不见的一场大雪铺天盖地的下着,白水河茶场的茶苗被雪封在雪层里,新封顶的厂房前天...

  • 灾后重建,不忘初心,继续

    磅礴大雨的突降 宁静了这座城市的喧闹 城市的绿色自然风光 和突袭的无情疫灾新况 天地乾坤这样被颠倒 欣赏雨后水面倒...

  • 付出总不会是空的

    2016-06-23 这几天忙着统计灾后受损情况,也忙着跑部门跑资金希望能够帮助我们进行灾后重建,还忙着组织镇村一...

网友评论

      本文标题:洛谷 P1119 灾后重建 题解

      本文链接:https://www.haomeiwen.com/subject/ygnztqtx.html