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

P2910 [USACO08OPEN] Clear And Present Danger S

Problem: P2910 [USACO08OPEN] Clear And Present Danger S

文章目录

  • 思路
  • 解题方法
  • 复杂度
  • Code

思路

这是一个图论问题,我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先,我们需要构建一个距离矩阵,然后使用Floyd-Warshall算法来更新这个矩阵,最后我们可以通过这个矩阵来找到最短路径。

解题方法

首先,我们需要读取输入数据,包括城市的数量n,路径的数量m,以及每个城市之间的距离。
然后,我们需要构建一个距离矩阵,初始化所有的距离为无穷大。
接下来,我们使用Floyd-Warshall算法来更新距离矩阵。这个算法的基本思想是,对于每个城市,我们尝试通过这个城市来更新其他城市之间的距离。如果通过这个城市可以使得其他城市之间的距离变短,那么我们就更新这个距离。
最后,我们可以通过距离矩阵来找到最短路径。我们只需要遍历路径,然后累加每两个城市之间的距离,就可以得到最短路径的长度。

复杂度

时间复杂度:

O ( n 3 ) O(n^3) O(n3),其中n是城市的数量。这是因为Floyd-Warshall算法的时间复杂度是 O ( n 3 ) O(n^3) O(n3)

空间复杂度:

O ( n 2 ) O(n^2) O(n2),其中n是城市的数量。这是因为我们需要一个n*n的矩阵来存储城市之间的距离。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = 110;static int MAXM = 100010;static int[] path = new int[MAXM];static int[][] distance = new int[MAXN][MAXN];static int n, m, ans;public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();for (int i = 0; i < m; i++) {path[i] = nextInt() - 1;}build();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {distance[i][j] = nextInt();}}floyd();ans = 0;for (int i = 1; i < m; i++) {ans += distance[path[i - 1]][path[i]];}out.println(ans);out.flush();}private static void floyd() {// TODO Auto-generated method stubfor(int bridge = 0; bridge < n; bridge++) {for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {if(distance[i][bridge] != Integer.MAX_VALUE && distance[bridge][j] != Integer.MAX_VALUE&& distance[i][j] > distance[i][bridge] + distance[bridge][j]) {distance[i][j] = distance[i][bridge] + distance[bridge][j];}}}}}private static void build() {// TODO Auto-generated method stubfor (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {distance[i][j] = Integer.MAX_VALUE;}}}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}

相关文章:

P2910 [USACO08OPEN] Clear And Present Danger S

Problem: P2910 [USACO08OPEN] Clear And Present Danger S 文章目录 思路解题方法复杂度Code 思路 这是一个图论问题&#xff0c;我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先&#xff0c;我们需要构建一个距离矩阵&am…...

ES6 对象方面的新特性

ES6&#xff08;ECMAScript 2015&#xff09;为JavaScript语言增加了很多新特性&#xff0c;包括对象字面量属性的简写、计算属性名、方法的简写、对象的解构赋值、Object.assign()方法复制对象属性、Object.is()比较两个值等。以下是一些在ES6中经常使用的对象方法&#xff1a…...

GO语言核心30讲 进阶技术 (第一部分)

原站地址&#xff1a;Go语言核心36讲_Golang_Go语言-极客时间 一、数组和切片 1. 两者最大的不同&#xff1a;数组的长度是固定的&#xff0c;而切片的长度是可变的。 2. 可以把切片看成是对数组的一层封装&#xff0c;因为每个切片的底层数据结构中&#xff0c;一定会包含一…...

[力扣题解]225. 用队列实现栈

题目&#xff1a;225. 用队列实现栈 思路 用一个队列模拟栈&#xff1b; 假设有数字&#xff1a;1&#xff0c;2&#xff0c;3&#xff1b; pop 队列里是这样的存的&#xff1a;3&#xff0c;2&#xff0c;1&#xff1b; 作为一个栈&#xff0c;应该弹出最后进来的那一个3&…...

Leetcode—2105. 给植物浇水 II【中等】

2024每日刷题&#xff08;131&#xff09; Leetcode—2105. 给植物浇水 II 实现代码 class Solution { public:int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {int size plants.size();int i 0;int j size - 1;int capA capacityA;in…...

wordpress外贸建站公司歪建站新版网站上线

wordpress外贸建站公司 歪猫建站 歪猫WordPress外贸建站&#xff0c;专业从事WordPress多语言外贸小语种网站建设与外贸网站海个推广、Google SEO搜索引擎优化等服务。 https://www.waimaoyes.com/dongguan...

关于二手车系统学习--登录模块

1.样式1-17行 <div class="cheader"><div style="width: 80%;margin: 0 auto;line-height: 50px;padding-top: 10px"><el-row><el-col:span="5"style="font-size: 20px;cursor: pointer;color: #00ae66;font-weight: …...

若依生成代码的步骤

1.创建表&#xff0c;要有注释 2.导入表 3.创建主菜单 4.修改表 5.生成代码 6.把代码复制到自己的程序中&#xff1a;复制表、后端、前端 7.重启后端&#xff0c;如果有问题则clean 8.回到浏览器可以看到正常显示了生成的页面...

深度学习论文: LightGlue: Local Feature Matching at Light Speed

深度学习论文: LightGlue: Local Feature Matching at Light Speed LightGlue: Local Feature Matching at Light Speed PDF: https://arxiv.org/pdf/2306.13643 PyTorch代码: https://github.com/shanglianlm0525/CvPytorch PyTorch代码: https://github.com/shanglianlm0525/…...

全面解析C++11与C++20线程(含内容)

昨晚跟一些小伙伴做了第一次直播尝试&#xff0c;一起探讨了C11 thread与 C20的jthread&#xff0c;于此同时给大家出了几个问题&#xff0c;在直播之外不会公布答案&#xff0c;所以以后直播还是得跟着走起。 总共有22人参加直播&#xff0c;氛围相当不错&#xff0c;没有录播…...

【八股】消息中间件

通用MQ问题 使用场景 异步发送(验证码、短信、邮件)MYSQL和Redis,ES之间的数据同步分布式事务削峰填谷消息的重复消费问题 👉定义:消费者已经消费了消息,但是可能由于网络抖动或者消费者挂了导致ack回执没有发送给MQ 👉解决方案 为每条消息设置一个唯一的标识id,在…...

【17-Ⅰ】Head First Java 学习笔记

HeadFirst Java 本人有C语言基础&#xff0c;通过阅读Java廖雪峰网站&#xff0c;简单速成了java&#xff0c;但对其中一些入门概念有所疏漏&#xff0c;阅读本书以弥补。 第一章 Java入门 第二章 面向对象 第三章 变量 第四章 方法操作实例变量 第五章 程序实战 第六章 Java…...

weblogic 反序列化 [CVE-2017-10271]

一、漏洞描述 这个漏洞是wls-wsat这个接口出了问题&#xff0c;Weblogic的WLS Security组件对外提供webservice服务&#xff0c;其中使用了XMLDecoder来解析用户传入的XML数据&#xff0c;在解析的过程中出现反序列化漏洞&#xff0c;导致可执行任意命令。攻击者发送精心构造的…...

CoPilot 产品体验:提升 OpenNJet 的控制管理和服务提供能力

文章目录 前言系统架构介绍CoPilot 配置CoPilot 插件规范 体验 CoPilot 实例CoPilot: Broker 实例CoPilot: Ctrl 实例 开发其他语言编写的 CoPilot目标主要思路具体实现执行 go 程序代码 功能扩展总结 前言 CoPilot 是 OpenNJet 的一个重要组成部分&#xff0c;它在 Master-Wo…...

Leetcode 第396场周赛 问题和解法

问题 有效单词 有效单词需要满足以下几个条件&#xff1a; 至少包含3个字符。 由数字0-9和英文大小写字母组成。&#xff08;不必包含所有这类字符。&#xff09; 至少包含一个元音字母。 至少包含一个辅音字母。 给你一个字符串word。如果word是一个有效单词&#xff0c;则…...

OC foudation框架(上)学习

foundation框架 文章目录 foundation框架字符串&#xff08;NSString && NSMutableString&#xff09;NSString的其他功能NSMutableString 日期与时间 &#xff08;NSDate&#xff09;2.1 日期与时间&#xff08;NSDate&#xff09;2.2日期格式器日历与日期组件定时器&…...

【机器学习300问】83、深度学习模型在进行学习时梯度下降算法会面临哪些局部最优问题?

梯度下降算法是一种常用的优化方法&#xff0c;用于最小化损失函数以训练模型。然而&#xff0c;在使用梯度下降算法时&#xff0c;可能会面临以下局部最优问题。 &#xff08;一&#xff09;非凸函数的局部极小值 问题描述&#xff1a;在复杂的损失函数中&#xff0c;如果目…...

基于springboot的校园管理系统源码数据库

基于springboot的校园管理系统源码数据库 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;校园管理系统当然也不能排除在外。校园管理系统是以实际运用为开发背景&#xff0c;…...

图形网络的自适应扩散 笔记

1 Title Adaptive Diffusion in Graph Neural Networks&#xff08;Jialin Zhao、Yuxiao Dong、Ming Ding、Evgeny Kharlamov、Jie Tang&#xff09;【NIPS 2021】 2 Conclusion The neighborhood size in GDC is manually tuned for each graph by conductin…...

vue基础配置

vite.config.ts import { defineConfig } from vite import vue from vitejs/plugin-vue import path from "path"; //引入svg需要用到的插件 import { createSvgIconsPlugin } from vite-plugin-svg-icons //mock插件提供方法 import { viteMockServe } from vite-…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

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

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

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...