洛谷 P4568 [JLOI2011] 飞行路线 pytho解析

2023-11-20 19:36

本文主要是介绍洛谷 P4568 [JLOI2011] 飞行路线 pytho解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

P4568 [JLOI2011] 飞行路线 pytho解析

时间:2023.11.20
题目地址:[JLOI2011] 飞行路线

题目分析

对于这个题呢就是最短路的问题了。那就可以用Dijkstra 算法,唯一不同的地方就是有免费的机票次数,那我们就先不考虑这个,就当次数为0。见代码①。这样就是一个比较模板的最短路问题了。
那现在要考虑到有免费的次数,那么就要将ans数组进行改变,引入一个次数即可,见代码②。看看代码的变化,理解清楚即可。
但是提交超时了,呃,只能说python是这样的,哈哈哈哈哈。
重在理解思路。
1

代码

① 假设免费机票次数为0

from queue import PriorityQueuen, m, k = map(int, input().split())
s, t = map(int, input().split())
e = [[] for _ in range(n)]
for _ in range(m):a, b, c = map(int, input().split())e[a].append((b, c))e[b].append((a, c))pq = PriorityQueue()
ans = [float('inf')]*n
vis = set()
pq.put((0, s))
ans[s] = 0
while not pq.empty():_, u = pq.get()if u in vis:continuevis.add(u)for v, w in e[u]:if ans[v] > ans[u] + w:ans[v] = ans[u] + wpq.put((ans[v], v))print(ans[t])     

② 超时,过70%

from queue import PriorityQueuen, m, k = map(int, input().split())
s, t = map(int, input().split())
e = [[] for _ in range(n)]
for _ in range(m):a, b, c = map(int, input().split())e[a].append((b, c))e[b].append((a, c))pq = PriorityQueue()
ans = [[float('inf')]*(k+1) for _ in range(n)]  # 引入cnt
vis = set()
pq.put((0, s, 0))     # 初始cnt为0
for i in range(k+1):ans[s][i] = 0
while not pq.empty():_, u, nowcnt = pq.get()if (u, nowcnt) in vis:continuevis.add((u,nowcnt))for v, w in e[u]:if nowcnt < k and ans[v][nowcnt+1] > ans[u][nowcnt]:ans[v][nowcnt+1] = ans[u][nowcnt]pq.put((ans[v][nowcnt+1], v, nowcnt+1))if ans[v][nowcnt] > ans[u][nowcnt] + w:ans[v][nowcnt] = ans[u][nowcnt] + wpq.put((ans[v][nowcnt], v, nowcnt))print(min(ans[t]))     

这篇关于洛谷 P4568 [JLOI2011] 飞行路线 pytho解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/396943

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提

Java中的runnable 和 callable 区别解析

《Java中的runnable和callable区别解析》Runnable接口用于定义不需要返回结果的任务,而Callable接口可以返回结果并抛出异常,通常与Future结合使用,Runnab... 目录1. Runnable接口1.1 Runnable的定义1.2 Runnable的特点1.3 使用Ru

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente