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

蓝桥杯每日一题(floyd算法)

4074 铁路与公路

如果两个城市之间有铁路t1=1,公路就会t2>1,没铁路的时候t1>1,公路t2=1。也就是公路铁路永远都不会相等。我们只需要计算通过公路和铁路从1到n最大的那个即可。

floyd是直接在数组上更新距离。不需要新建dis数组。另外一定要记得把邻接矩阵初始化为无穷

#include<bits/stdc++.h>
using namespace std;
//4074铁路与公路
const int N=410,M=79810;
int p[N][N],r[N][N];
int n,m;
int floyd(int a[][N])//走公路或者走铁路的最短路
{if(a[1][n]==1)return 1;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]>a[i][k]+a[k][j]){a[i][j]=a[i][k]+a[k][j];}}}}return a[1][n];
}
int main()
{cin>>n;cin>>m;//一定要先把图初始化为无穷后面floyd直接在图上进行更新memset(p,0x3f,sizeof(p));memset(r,0x3f,sizeof(r));while(m--){int x,y;cin>>x>>y;p[x][y]=p[y][x]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j&&p[i][j]!=1){r[i][j]=1;}}}int ans=max(floyd(p),floyd(r));if(ans==0x3f3f3f3f){cout<<-1<<endl;}else{cout<<ans<<endl;}
}

854 Floyd求最短路

1、关于为什么是INF/2

2、为什么输入边的时候要min

因为发现输入里面可以重复输入相同边为不同的值。只保留最小的即可。 

#include<bits/stdc++.h>
using namespace std;
//4074铁路与公路
const int N=210,INF=0x3f3f3f3f;
int p[N][N];
int n,m,k;
void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){p[i][j]=min(p[i][j],p[i][k]+p[k][j]);}}}
}
int main()
{cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)p[i][j]=0;else{p[i][j]=INF;}}}while(m--){int x,y,v;cin>>x>>y>>v;p[x][y]=min(p[x][y],v);}floyd();while(k--){int x,y;cin>>x>>y;if(p[x][y]<INF/2){cout<<p[x][y]<<endl;}else{cout<<"impossible"<<endl;}}}

相关文章:

蓝桥杯每日一题(floyd算法)

4074 铁路与公路 如果两个城市之间有铁路t11&#xff0c;公路就会t2>1,没铁路的时候t1>1,公路t21。也就是公路铁路永远都不会相等。我们只需要计算通过公路和铁路从1到n最大的那个即可。 floyd是直接在数组上更新距离。不需要新建dis数组。另外一定要记得把邻接矩阵初始…...

文心一言 VS 讯飞星火 VS chatgpt (224)-- 算法导论16.3 6题

六、假定我们有字母表 C{0&#xff0c;1&#xff0c;…&#xff0c;n-1} 上的一个最优前缀码&#xff0c;我们希望用最少的二进制位传输此编码。说明如何仅用 2n-1n⌈lgn⌉ 位表示 C 上的任意最优前缀码。(提示&#xff1a;通过对树的遍历&#xff0c;用 2n-1 位说明编码树的结…...

flutter3_douyin:基于flutter3+dart3短视频直播实例|Flutter3.x仿抖音

flutter3-dylive 跨平台仿抖音短视频直播app实战项目。 全新原创基于flutter3.19.2dart3.3.0getx等技术开发仿抖音app实战项目。实现了类似抖音整屏丝滑式上下滑动视频、左右滑动切换页面模块&#xff0c;直播间进场/礼物动效&#xff0c;聊天等模块。 运用技术 编辑器&#x…...

VR全景赋能智慧农业,打造沉浸式种植体验平台

随着人口的增长&#xff0c;传统农业也正在面临着不一样的挑战&#xff0c;加上很多人对农业的固有印象&#xff0c;很少有年轻人愿意下到农田里&#xff0c;那么该如何提高产量、降低成本以及引导年轻人深刻感受现代农业成为了急需解决的问题。 随着城市化脚步的推进&#xff…...

百度文心一言(ERNIE bot)API接入Android应用

百度文心一言&#xff08;ERNIE bot&#xff09;API接入Android应用实践 - 拾一贰叁 - 博客园 (cnblogs.com) Preface: 现在生成式AI越来越强大了&#xff0c;想在android上实现一个对话助手的功能&#xff0c;大概摸索了一下接入百度文心一言API的方法。 与AI助手交换信息的…...

springboot基本使用八(mbatisplus+filter实现登录功能)

mybatisplus依赖: <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.4.2</version> </dependency> mysql依赖: <dependency><groupId>com.mysql<…...

蚂蚁庄园今天答案

蚂蚁庄园是一款爱心公益游戏&#xff0c;用户可以通过喂养小鸡&#xff0c;产生鸡蛋&#xff0c;并通过捐赠鸡蛋参与公益项目。用户每日完成答题就可以领取鸡饲料&#xff0c;使用鸡饲料喂鸡之后&#xff0c;会可以获得鸡蛋&#xff0c;可以通过鸡蛋来进行爱心捐赠。其中&#…...

第5章 数据建模和设计

思维导图 5.1 引言 最常见的6种模式&#xff1a;关系模式、多维模式、面向对象模式、 事实模式、时间序列模式和NoSQL模式 每种模式分为三层模型&#xff1a;概念模型、逻辑模型和物理模型 每种模型都包含一系列组件&#xff1a;如实体、关系、事实、键和属性。 5.1.1 业务驱…...

牛客NC108 最大正方形【中等 动态规划 Java,Go,PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e 思路 动态规划: 先初始化第一行和第一列。然后其他单元格依赖自己的上边&#xff0c;左边和左上角参考答案Java import java.util.*;public class Solution {/*** 代码中的类…...

C#学生信息成绩管理系统

一、系统功能描述 本系统包括两类用户&#xff1a;学生、管理员。管理员可以通过系统来添加管理员信息、修改管理员信息、添加学生信息、修改学生信息&#xff1b;开设课程、查询课程、录入成绩、统计成绩、修改成绩、修改个人密码等&#xff0c;而学生则可以通过系统来选择课…...

精品凉拌菜系列热卤系列课程

这一系列课程涵盖精美凉拌菜和美味热卤菜的制作技巧。学员将学习如何选材、调味和烹饪&#xff0c;打造口感丰富、色香俱佳的菜肴。通过实践训练&#xff0c;掌握独特的烹饪技能&#xff0c;为家庭聚餐或职业厨艺提升增添亮点。 课程大小&#xff1a;6.6G 课程下载&#xff1…...

Java代码基础算法练习-求一个三位数的各位数字之和-2024.03.27

任务描述&#xff1a; 输入一个正整数n&#xff08;取值范围&#xff1a;100<n<1000&#xff09;&#xff0c;然后输出每位数字之和 任务要求&#xff1a; 代码示例&#xff1a; package M0317_0331;import java.util.Scanner;public class m240327 {public static voi…...

Excel 十字交叉聚光灯查询,再也不用担心看串行与列

当Excel表格行列较多时&#xff0c;要想跟条件找到目标数据可以用查找引用函数自动调取&#xff0c;如果又想让找出来的结果突出显示&#xff0c;有什么好办法呢&#xff1f; 先来看一个做好的案例效果&#xff0c;用户选择查询条件后&#xff0c;结果突出显示。 当查询条件变…...

集合和字符串的使用

文章目录 一、集合概述二、Collection2.1 List接口2.2 Set接口&#xff08;不常用&#xff09;2.2.1 TreeSet 三、Map接口四、Collections工具类五、String六、String类型转换6.1 基本数据类型6.2 基本数据类型、包装类 --> String6.3 String与char[]6.4 String与byte[] 一、…...

Wagtail-基于Python Django的内容管理系统CMS实现公网访问

目录 ⛳️推荐 前言 1. 安装并运行Wagtail 1.1 创建并激活虚拟环境 2. 安装cpolar内网穿透工具 3. 实现Wagtail公网访问 4. 固定Wagtail公网地址 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给…...

Python入门级题目及答案

前言&#xff1a; 学习Python作为一门编程语言是非常有必要的&#xff0c;因为Python简单易学&#xff0c;功能强大&#xff0c;应用广泛。在本篇博客中&#xff0c;我们将提供八道Python入门级的题目&#xff0c;每道题目都伴有详细的描述和对应的答案代码。通过完成这八道题目…...

【C语言基础】:字符串函数(二)

文章目录 一、strncpy函数的使用二、strncat函数的使用三、strncmp函数的使用四、strstr函数的使用和模拟实现4.1 strstr函数的使用4.2 strstr函数的模拟实现 五、strtok函数的使用六、strerror函数的使用 书山有路勤为径&#xff0c;学海无涯苦作舟。 创作不易&#xff0c;宝子…...

【Docker】Docker资源(创建容器)CPU/内存/磁盘IO/GPU限制与分配教程

Docker资源创建容器CPU/内存/磁盘IO/GPU限制与分配 一、关键概念解释二、Docker分配CPU资源限制三、Docker分配内存资源限制四、Docker容器中对磁盘IO进行限制五、Docker对GPU资源限制管理 一、关键概念解释 【cgroup】 cgroups名称源自控制组群&#xff08;control g…...

发展规划--IM系统

1、时代背景 5G应用&#xff0c;多终端应用&#xff0c;物联网应用&#xff0c;小程序&#xff0c;工业互联&#xff0c;大数据应用等等大前端时代的到来&#xff0c;程序员不能只关注crud&#xff0c;因为以后的服务并发量只会越来越多。 高并发架构师、大数据架构师或者说j…...

stm32平衡车

目录 一.所需材料 二.PID算法&#xff08;简单说明&#xff09; 直立环 速度环 串级PID 三.使用到的外设 1.定时器输出比较-PWM 2.定时器编码器模式 3.编码器读取速度 4.电机驱动函数 5.外部中断 四、小车 调试 一.所需材料 1.陀螺仪MPU6050--读取三轴的加速度…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...