2018 ccpc 女生赛 奢侈的旅行 (堆优化dijkstra)

2024-03-03 04:48

本文主要是介绍2018 ccpc 女生赛 奢侈的旅行 (堆优化dijkstra),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

奢侈的旅行

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 394    Accepted Submission(s): 78


Problem Description
高玩小Q不仅喜欢玩寻宝游戏,还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有 n个城镇,编号依次为 1 n

这些城镇之间有 m条单向道路,第 i 条单项道路包含四个参数 ui,vi,ai,bi,表示一条从 ui号城镇出发,在 vi号城镇结束的单向道路,因为是单向道路,这不意味着小Q可以从 vi沿着该道路走到 ui。小Q的初始等级 level 1,每当试图经过一条道路时,需要支付 cost=log2level+ailevel点积分,并且经过该道路后,小Q的等级会提升 ai级,到达 level+ai级。但是每条道路都会在一定意义上歧视低消费玩家,准确地说,如果该次所需积分 cost<bi,那么小Q不能经过该次道路,也不能提升相应的等级。

注意:本游戏中等级为正整数,但是积分可以是任意实数。

小Q位于 1号城镇,等级为 1,现在为了做任务要到 n号城镇去。这将会是一次奢侈的旅行,请写一个程序帮助小Q找到需要支付的总积分最少的一条路线,或判断这是不可能的。

Input
第一行包含一个正整数 T(1T30),表示测试数据的组数。

每组数据第一行包含两个整数 n,m(2n100000,1m200000),表示城镇数和道路数。

接下来 m行,每行四个整数 ui,vi,ai,bi(1ui,vin,uivi,0ai109,0bi60),分别表示每条单向道路。

Output
对于每组数据,输出一行一个整数,即最少所需的总积分的整数部分,如: 4.9999输出 4 1.0输出 1。若不存在合法路线请输出 1

Sample Input
 
1 3 3 1 2 3 2 2 3 1 6 1 3 5 0

Sample Output
 
2

Source
"字节跳动杯"2018中国大学生程序设计竞赛-女生专场


从题意可以看出来这是一个最短路的问题,初始等级为1,所以总积分的计算可以用对数化简成log((1+a1)/1 * (1+a1+a2)/(1+a1)......)--->log(1+a1+a2+....an)。所以过程中计算总积分时先计算 1+cost ,最后再求log就可以。

spfa会超时。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n, m;
int head[200006], cnt;
struct Edge{int v, a, b, next;
}edge[200006];void add(int u, int v, int a, int b){edge[cnt].a = a;edge[cnt].b = b;edge[cnt].v = v;edge[cnt].next = head[u];head[u] = cnt++;
}struct node{int id;ll level;node(int id, ll level){this->id = id;this->level = level;}bool operator < (const node &x)const{return level > x.level;}
};
ll dis[100005];
int vis[100005];
int dijkstra(){memset(dis, INF, sizeof(dis));memset(vis, 0 ,sizeof(vis));priority_queue<node>q;q.push(node(1, 1));dis[1] = 1;while(!q.empty()){node temp = q.top();q.pop();int u = temp.id;if(u == n)for(int i = 1; i < 65; i++)if((1ll << i) > temp.level)return i - 1;if(vis[u])continue;vis[u] = 1;for(int i = head[u]; i != -1; i = edge[i].next){if((temp.level + edge[i].a) / temp.level >= (1ll << edge[i].b) && temp.level + edge[i].a < dis[edge[i].v]){dis[edge[i].v] = temp.level + edge[i].a;q.push(node(edge[i].v, dis[edge[i].v]));}}}return -1;
}int main(){int T, u, v, a, b;scanf("%d", &T);while(T--){cnt = 0;memset(head, -1, sizeof(head));scanf("%d%d", &n, &m);for(int i = 0; i < m; i++){scanf("%d%d%d%d", &u, &v, &a, &b);add(u, v, a, b);}printf("%d\n", dijkstra());}return 0;
}



这篇关于2018 ccpc 女生赛 奢侈的旅行 (堆优化dijkstra)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案

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

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

使用国内镜像源优化pip install下载的方法步骤

《使用国内镜像源优化pipinstall下载的方法步骤》在Python开发中,pip是一个不可或缺的工具,用于安装和管理Python包,然而,由于默认的PyPI服务器位于国外,国内用户在安装依赖时可... 目录引言1. 为什么需要国内镜像源?2. 常用的国内镜像源3. 临时使用国内镜像源4. 永久配置国内镜

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

Deepseek使用指南与提问优化策略方式

《Deepseek使用指南与提问优化策略方式》本文介绍了DeepSeek语义搜索引擎的核心功能、集成方法及优化提问策略,通过自然语言处理和机器学习提供精准搜索结果,适用于智能客服、知识库检索等领域... 目录序言1. DeepSeek 概述2. DeepSeek 的集成与使用2.1 DeepSeek API

Tomcat高效部署与性能优化方式

《Tomcat高效部署与性能优化方式》本文介绍了如何高效部署Tomcat并进行性能优化,以确保Web应用的稳定运行和高效响应,高效部署包括环境准备、安装Tomcat、配置Tomcat、部署应用和启动T... 目录Tomcat高效部署与性能优化一、引言二、Tomcat高效部署三、Tomcat性能优化总结Tom