当前位置: 首页 > 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. 下载和安装小程序开…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

6.9-QT模拟计算器

源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...