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

相关文章

小白也能轻松上手! 路由器设置优化指南

《小白也能轻松上手!路由器设置优化指南》在日常生活中,我们常常会遇到WiFi网速慢的问题,这主要受到三个方面的影响,首要原因是WiFi产品的配置优化不合理,其次是硬件性能的不足,以及宽带线路本身的质... 在数字化时代,网络已成为生活必需品,追剧、游戏、办公、学习都离不开稳定高速的网络。但很多人面对新路由器

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

Linux进程CPU绑定优化与实践过程

《Linux进程CPU绑定优化与实践过程》Linux支持进程绑定至特定CPU核心,通过sched_setaffinity系统调用和taskset工具实现,优化缓存效率与上下文切换,提升多核计算性能,适... 目录1. 多核处理器及并行计算概念1.1 多核处理器架构概述1.2 并行计算的含义及重要性1.3 并

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

PyTorch高级特性与性能优化方式

《PyTorch高级特性与性能优化方式》:本文主要介绍PyTorch高级特性与性能优化方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、自动化机制1.自动微分机制2.动态计算图二、性能优化1.内存管理2.GPU加速3.多GPU训练三、分布式训练1.分布式数据

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索

C#实现高性能Excel百万数据导出优化实战指南

《C#实现高性能Excel百万数据导出优化实战指南》在日常工作中,Excel数据导出是一个常见的需求,然而,当数据量较大时,性能和内存问题往往会成为限制导出效率的瓶颈,下面我们看看C#如何结合EPPl... 目录一、技术方案核心对比二、各方案选型建议三、性能对比数据四、核心代码实现1. MiniExcel

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.