蓝桥杯每日一题(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,公路就会t2>1,没铁路的时候t1>1,公路t21。也就是公路铁路永远都不会相等。我们只需要计算通过公路和铁路从1到n最大的那个即可。 floyd是直接在数组上更新距离。不需要新建dis数组。另外一定要记得把邻接矩阵初始…...

文心一言 VS 讯飞星火 VS chatgpt (224)-- 算法导论16.3 6题
六、假定我们有字母表 C{0,1,…,n-1} 上的一个最优前缀码,我们希望用最少的二进制位传输此编码。说明如何仅用 2n-1n⌈lgn⌉ 位表示 C 上的任意最优前缀码。(提示:通过对树的遍历,用 2n-1 位说明编码树的结…...

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

VR全景赋能智慧农业,打造沉浸式种植体验平台
随着人口的增长,传统农业也正在面临着不一样的挑战,加上很多人对农业的固有印象,很少有年轻人愿意下到农田里,那么该如何提高产量、降低成本以及引导年轻人深刻感受现代农业成为了急需解决的问题。 随着城市化脚步的推进ÿ…...

百度文心一言(ERNIE bot)API接入Android应用
百度文心一言(ERNIE bot)API接入Android应用实践 - 拾一贰叁 - 博客园 (cnblogs.com) Preface: 现在生成式AI越来越强大了,想在android上实现一个对话助手的功能,大概摸索了一下接入百度文心一言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<…...

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

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

牛客NC108 最大正方形【中等 动态规划 Java,Go,PHP】
题目 题目链接: https://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e 思路 动态规划: 先初始化第一行和第一列。然后其他单元格依赖自己的上边,左边和左上角参考答案Java import java.util.*;public class Solution {/*** 代码中的类…...

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

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

Java代码基础算法练习-求一个三位数的各位数字之和-2024.03.27
任务描述: 输入一个正整数n(取值范围:100<n<1000),然后输出每位数字之和 任务要求: 代码示例: package M0317_0331;import java.util.Scanner;public class m240327 {public static voi…...

Excel 十字交叉聚光灯查询,再也不用担心看串行与列
当Excel表格行列较多时,要想跟条件找到目标数据可以用查找引用函数自动调取,如果又想让找出来的结果突出显示,有什么好办法呢? 先来看一个做好的案例效果,用户选择查询条件后,结果突出显示。 当查询条件变…...
集合和字符串的使用
文章目录 一、集合概述二、Collection2.1 List接口2.2 Set接口(不常用)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公网地址 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给…...
Python入门级题目及答案
前言: 学习Python作为一门编程语言是非常有必要的,因为Python简单易学,功能强大,应用广泛。在本篇博客中,我们将提供八道Python入门级的题目,每道题目都伴有详细的描述和对应的答案代码。通过完成这八道题目…...

【C语言基础】:字符串函数(二)
文章目录 一、strncpy函数的使用二、strncat函数的使用三、strncmp函数的使用四、strstr函数的使用和模拟实现4.1 strstr函数的使用4.2 strstr函数的模拟实现 五、strtok函数的使用六、strerror函数的使用 书山有路勤为径,学海无涯苦作舟。 创作不易,宝子…...
【Docker】Docker资源(创建容器)CPU/内存/磁盘IO/GPU限制与分配教程
Docker资源创建容器CPU/内存/磁盘IO/GPU限制与分配 一、关键概念解释二、Docker分配CPU资源限制三、Docker分配内存资源限制四、Docker容器中对磁盘IO进行限制五、Docker对GPU资源限制管理 一、关键概念解释 【cgroup】 cgroups名称源自控制组群(control g…...

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

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

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

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

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。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爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...