当前位置: 首页 > news >正文

【洛谷千题详解】P1613 跑路

目录

题目总览

题目描述

输入格式

输出格式

思路分析

AC代码


题目总览

题目描述

小 A 的工作不仅繁琐,更有苛刻的规定,要求小 A 每天早上在 6:00 之前到达公司,否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资,小 A 买了一个空间跑路器,每秒钟可以跑 2k 千米(k 是任意自然数)。当然,这个机器是用 longint 存的,所以总跑路长度不能超过 maxlongint 千米。小 A 的家到公司的路可以看做一个有向图,小 A 家为点 1,公司为点 n,每条边长度均为一千米。小 A 想每天能醒地尽量晚,所以让你帮他算算,他最少需要几秒才能到公司。数据保证 1 到 n 至少有一条路径。

输入格式

第一行两个整数 n,m,表示点的个数和边的个数。

接下来 m 行每行两个数字 u,v,表示一条 u 到 v 的边。

输出格式

一行一个数字,表示到公司的最少秒数。

思路分析

图论中FLoyd模版题。

AC代码

#include<bits/stdc++.h>
using namespace std;
bool f[64][55][55];
int n,m,d[55][55];
int main(){cin>>n>>m;for (int i=1;i<=m;i++){int x,y; cin>>x>>y;f[0][x][y]=1;}for (int k=1;k<=63;k++){for (int x=1;x<=n;x++){for (int y=1;y<=n;y++){f[k][x][y]=0;for (int z=1;z<=n;z++){if (f[k-1][x][z]&&f[k-1][z][y]) f[k][x][y]=1;}}}}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){d[i][j]=1e9;{for (int k=0;k<=63;k++) {if (f[k][i][j]) {d[i][j]=1;}}}}}for (int k=1;k<=n;k++){for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}cout<<d[1][n]<<endl;return 0;
}

相关文章:

【洛谷千题详解】P1613 跑路

目录 题目总览 题目描述 输入格式 输出格式 思路分析 AC代码 题目总览 题目描述 小 A 的工作不仅繁琐&#xff0c;更有苛刻的规定&#xff0c;要求小 A 每天早上在 6:00 之前到达公司&#xff0c;否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的…...

如何定义resultType和resultMap,它们之间的区别是什么?解释一下<parameterType>的作用和用法。

在MyBatis中&#xff0c;resultType和resultMap都用于将数据库查询结果映射到Java对象&#xff0c;但它们在使用方式和灵活性上有一些区别。 resultType resultType是一个简单的类型别名&#xff0c;它用于指定查询结果应该映射到的Java类型。当数据库表中的列名和Java对象的属…...

Docker:部署微服务集群

1. 部署微服务集群 实现思路&#xff1a; ① 查看课前资料提供的cloud-demo文件夹&#xff0c;里面已经编写好了docker-compose文件 ② 修改自己的cloud-demo项目&#xff0c;将数据库、nacos地址都命名为docker-compose中的服务名 ③ 使用maven打包工具&#xff0c;将项目…...

傅里叶变换pytorch使用

参考视频&#xff1a;1 傅里叶变换原理_哔哩哔哩_bilibili 傅里叶变换是干嘛的&#xff1a; 傅里叶得到低频、高频信息&#xff0c;针对低频、高频处理能够实现不同的目的。 傅里叶过程是可逆的&#xff0c;图像经过傅里叶变换、逆傅里叶变换后&#xff0c;能够恢复到原始图像…...

LeetCode104 二叉树的最大深度

题目 给定一个二叉树 root &#xff0c;返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例 2&#xff1a; 输入&#xff1a;root [1,null,…...

使用Spring的AOP

使用Spring的AOP 一、AOP 的常用注解1.切面类Aspect2.Pointcut3.前置通知Before4.后置通知AfterReturning5.环绕通知Around6.异常通知AfterThrowing7.最终通知After8.切面顺序Order9.启用自动代理EnableAspectJAutoProxy 二、AOP注解方式开发三、AOP 全注解开发四、基于XML配置…...

爬虫之矛---JavaScript基石篇3<JavaScript构造函数的内部机制和应用(2)>

前言: 继续上一篇https://blog.csdn.net/m0_56758840/article/details/136592611 正文: 1.ES6中的类和构造函数的对应关系 A. 介绍ES6引入的类的概念和语法糖 类的概念&#xff1a; ES6引入了类&#xff08;class&#xff09;的概念&#xff0c;类是一种抽象的数据类型&…...

_note_05

1.说一说什么是函数重载&#xff1f; 函数签名相同除了 形参不同数据类型 函数签名相同除了 形参不同个数 2.void关键字的作用&#xff1f;返回值是void &#xff0c;可以写return 吗&#xff1f; 函数无返回&#xff0c;使用void修饰; 可以只使用return使函数结束; 3.按要…...

将格蠹GDK8的cmake3.10升级为cmake3.15

#升级过程# 1、wget https://cmake.org/files/v3.15/cmake-3.15.0-rc1.tar.gz 2、tar -zxvf cmake-3.15.0-rc1.tar.gz 3 、cd cmake-3.15.0-rc1 4、./configure 5、sudo make install 6、reboot 7、查看cmake版本&#xff1a; geduergdk8:~$ cmake --version cmake ve…...

b树(一篇文章带你 理解 )

目录 一、引言 二、B树的基本定义 三、B树的性质与操作 1 查找操作 2 插入操作 3 删除操作 四、B树的应用场景 1 数据库索引 2 文件系统 3 网络路由表 五、哪些数据库系统不使用B树进行索引 1 列式数据库 2 图形数据库 3 内存数据库 4 NoSQL数据库 5 分布式数据…...

OD_2024_C卷_200分_7、5G网络建设【JAVA】【最小生成树】

package odjava;import java.util.Scanner;public class 七_5G网络建设 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt(); // 基站数量&#xff08;节点数&#xff09;int m sc.nextInt(); // 基站对数量&#xff08;边数&…...

面试题:分布式锁用了 Redis 的什么数据结构

在使用 Redis 实现分布式锁时&#xff0c;通常使用 Redis 的字符串&#xff08;String&#xff09;。Redis 的字符串是最基本的数据类型&#xff0c;一个键对应一个值&#xff0c;它能够存储任何形式的字符串&#xff0c;包括二进制数据。字符串类型的值最多可以是 512MB。 Re…...

【学习心得】websocket协议简介并与http协议对比

一、轮询和长轮询 在websocket协议出现之前&#xff0c;要想实现服务器和客户端的双向持久通信采取的是Ajax轮询。它的原理是每隔一段时间客户端就给服务器发送请求找服务器要数据。 让我们通过一个生活化的比喻来解释轮询和长轮询假设你正在与一位不怎么主动说话的老大爷&…...

基于Token的身份验证:安全与效率的结合

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…...

Electron程序如何在MacOS下获取相册访问权限

1.通过entitiment.plist&#xff0c;在electron-builder签名打包时&#xff0c;给app包打上签名。最后可以通过codesign命令进行验证。 TestPhotos.plist electron-builder配置文件中加上刚刚的plist文件。 通过codesign命令验证&#xff0c;若出现这个&#xff0c;则说明成…...

uniapp让输入框保持聚焦状态,不会失去焦点

使用场景&#xff1a;当输入框还有发送按钮的时候&#xff0c;点击发送希望软键盘不消失&#xff0c;还可以继续输入&#xff0c;或者避免因输入图片标签造成的屏闪问题 多次尝试后发现一个很实用的方法&#xff0c;适用input输入框和editor输入框 解决办法&#xff1a;把cli…...

面试中如何介绍mysql的B+树

B树是B树的变体&#xff0c;也是一颗多路搜索树。在MySQL中&#xff0c;B树是为磁盘或者其他直接辅助存储设备所设计的一种平衡的查找树结构。其具有以下特点&#xff1a; 每个节点最多有m个子女&#xff0c;m阶的B树深度最多为m。非根节点关键值个数范围是⌈m/2⌉-1<k<m…...

【Linux C | 网络编程】多播的概念、多播地址、UDP实现多播的C语言例子

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…...

AIGC实战——GPT(Generative Pre-trained Transformer)

AIGC实战——GPT 0. 前言1. GPT 简介2. 葡萄酒评论数据集3. 注意力机制3.1 查询、键和值3.2 多头注意力3.3 因果掩码 4. Transformer4.1 Transformer 块4.2 位置编码 5. 训练GPT6. GPT 分析6.1 生成文本6.2 注意力分数 小结系列链接 0. 前言 注意力机制能够用于构建先进的文本…...

微信小程序-入门

一.通过 Npm方式下载构建 1.下载和安装Npm&#xff1a;Npm https://docs.npmjs.com/downloading-and-installing-node-js-and-npm 或者 https://nodejs.org/en/download/ 未安装npm 提示 以下以安装node安装包为例 按任意键继续 安装完成后 2. 下载和安装小程序开…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...