首页 > 其他分享 >P1119 灾后重建

P1119 灾后重建

时间:2023-10-01 20:45:00浏览次数:39  
标签:int P1119 scanf Time 灾后 printf 0x3f3f3f3f 重建

题目传送:链接

思路

算法:\(Floyd.\)

  • 每次询问记录一个变量 \(n\),表示当前遍历到哪个点。
  • 当 \(t_n <= T\) 的时候,利用 \(n\) 点更新到 $(x,y) $ 点的最短路。
  • 如果发现 \(x,y\) 点其中有一个还没有修好,或者是 \(d_{x_y}\) 为 0x3f3f3f3f,就输出 \(-1\) 。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;
int t[N], d[N][N];
int n, m, q, Time, x, y, len, now;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t[i]);
        d[i][i] = 0; // 自己到自己的最短路为0
    }
    memset(d, 0x3f, sizeof(d)); // 初始化
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &len);
        d[x][y] = d[y][x] = len;
    }
    scanf("%d", &q);
    while (q--) { // q次询问
        scanf("%d%d%d", &x, &y, &Time);
        while (t[now] <= Time && now < n) { // 之前的点修好了,就用这个点更新最短路
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    d[i][j] = min(d[i][j], d[i][now] + d[now][j]);
                }
            }
            now++; // 点的编号自增
        }
        if (d[x][y] == INF || t[x] > Time || t[y] > Time) printf("-1\n"); // 走不到
        else printf("%d\n", d[x][y]);
    }
    return 0;
}

标签:int,P1119,scanf,Time,灾后,printf,0x3f3f3f3f,重建
From: https://www.cnblogs.com/yhx0322/p/17739247.html

相关文章

  • SLAM 深度估计 三维重建 标定 传感器融合
    经常有粉丝问视觉/激光/SLAM、三维重建等方向的学习路线,这里我再总结给大家,如下所示:随着最近几年智能机器人、自动驾驶、AR/MR等领域的快速发展,企业对3D视觉算法及SLAM算法需求越来越强烈,该领域迎来了爆发式发展。按照应用不同我们把3D视觉及SLAM算法分为如下方向:视觉深度估计视觉(......
  • MSSQL 维护小记(清理进程、重建索引)
    ------------------------------清理进程----------------------------------- declare@deleteSleepSessionnvarchar(100)--申明一个变量declaretablelistcursorlocal--申明一个本地游标forselect'kill'+rtrim(spid)frommaster.dbo.sysprocesses--数据库系统进......
  • PACS医学影像处理系统源码-虚拟内窥镜 三维重建技术
    PACS系统与医院HIS实现双向数据交换,自动从HIS系统获得病人基本信息、检查预约请求,自动向HIS系统传送预约请求接受、检查费用发生信息,接受来自HIS系统的检查结果查询和图像数据检索。医院医学影像PACS系统源码,集成三维影像后处理功能,包括三维多平面重建、三维容积重建、三维表面重建......
  • 剑指Offer面试题7:重建二叉树
    一、题目给定节点数为n的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。提示:1.vin.length== pre.length2.pre和vin 均无重复元素3.vin出现的元素均出现在 ......
  • 代码随想录算法训练营-贪心算法-4|406. 根据身高重建队列、452. 用最少数量的箭引爆
    406. 根据身高重建队列1. 一定要想如何确定一个维度,然后再按照另一个维度重新排列。2.先确定身高的维度,降序排列。3. 按照身高排序之后,优先按身高高的people的k来插入,后序插入节点也不会影响前面已经插入的节点,最终按照k的规则完成了队列。4. 局部最优:优先按身高高的peop......
  • 2.10 PE结构:重建重定位表结构
    Relocation(重定位)是一种将程序中的一些地址修正为运行时可用的实际地址的机制。在程序编译过程中,由于程序中使用了各种全局变量和函数,这些变量和函数的地址还没有确定,因此它们的地址只能暂时使用一个相对地址。当程序被加载到内存中运行时,这些相对地址需要被修正为实际的绝对地址,这......
  • 2.10 PE结构:重建重定位表结构
    Relocation(重定位)是一种将程序中的一些地址修正为运行时可用的实际地址的机制。在程序编译过程中,由于程序中使用了各种全局变量和函数,这些变量和函数的地址还没有确定,因此它们的地址只能暂时使用一个相对地址。当程序被加载到内存中运行时,这些相对地址需要被修正为实际的绝对地址,......
  • 2.9 PE结构:重建导入表结构
    脱壳修复是指在进行加壳保护后的二进制程序脱壳操作后,由于加壳操作的不同,有些程序的导入表可能会受到影响,导致脱壳后程序无法正常运行。因此,需要进行修复操作,将脱壳前的导入表覆盖到脱壳后的程序中,以使程序恢复正常运行。一般情况下,导入表被分为IAT(ImportAddressTable,导入地址表)......
  • 2.9 PE结构:重建导入表结构
    脱壳修复是指在进行加壳保护后的二进制程序脱壳操作后,由于加壳操作的不同,有些程序的导入表可能会受到影响,导致脱壳后程序无法正常运行。因此,需要进行修复操作,将脱壳前的导入表覆盖到脱壳后的程序中,以使程序恢复正常运行。一般情况下,导入表被分为IAT(ImportAddressTable,导入地址表......
  • 重建索引
    alert日志报错信息:[oracle@hd04trace]$catalert_db12c.log|grep"corrupt"-A2-B2|moreHexdumpof(file11,block704337)intracefile/app/oracle/diag/rdbms/orcl/db12c/trace/db12c_p006_20208.trcReadingdatafile'/app/oracle/oradata/orcl/d......