当前位置: 首页 > 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-…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

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

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

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...