“新华三杯”第十届成都信息工程大学ACM程序设计竞赛(同步赛)L. 怎么走啊(最短路+二分 分段函数)

本文主要是介绍“新华三杯”第十届成都信息工程大学ACM程序设计竞赛(同步赛)L. 怎么走啊(最短路+二分 分段函数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

登录—专业IT笔试面试备考平台_牛客网

思路来源

衡阳师范学院ac代码、pj学弟

题解

大致可以证明,在w从1e5减小到1的过程中,

之前某条反向边没有用到,现在需要用到反向边,也就是正向边用到的变少了

这样的变化有sqrt个,二分每个变化时的临界点,复杂度似乎是O(nsqrtnlognlogn)的

但是由于只关注1到n的最短路,临界点&二分的量级很难卡满,只能说O(能过)了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int ll
const int N=1e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
typedef pair<int,int> pii;
int n,m,d[N],st[N],ans[N],pre[N];
vector<array<int,3>> g[N];
int dijkstra(int W){for(int i=1;i<=n;i++) st[i]=0,d[i]=1e18;priority_queue<pii,vector<pii>,greater<pii>> q;q.push({0,1}); d[1]=0;while(!q.empty()){auto [dt,u]=q.top(); q.pop();if(st[u]) continue;st[u]=1;for(auto [j,w,f]:g[u]){int dis=dt;if(f) dis+=w*W;else dis+=w;if(d[j]>dis){d[j]=dis;pre[j]=u;q.push({d[j],j});}}}return d[n];
}
map<pii,int> mp;
int fun(){int cnt=0;for(int i=n;i;i=pre[i]) cnt+=mp[{pre[i],i}];return cnt;
}
void solve(){cin>>n>>m; for(int i=1;i<=m;i++){int u,v,w; cin>>u>>v>>w;g[u].push_back({v,w,0});g[v].push_back({u,w,1});mp[{u,v}]=0;mp[{v,u}]=w;}int L=1;while(L<=1e5){int l=L,r=1e5; int dis=dijkstra(l),sum=fun();while(l<r){int mid=(l+r+1)>>1;if(dijkstra(mid)==dis+(mid-L)*sum) l=mid;else r=mid-1;}for(int i=L;i<=l;i++) ans[i]=dis+(i-L)*sum;L=l+1;}int q; cin>>q;while(q--){int W; cin>>W;cout<<ans[W]<<endl;}
}
signed main(){IOS;int _=1;//cin>>_;while(_--){solve();}
}

这篇关于“新华三杯”第十届成都信息工程大学ACM程序设计竞赛(同步赛)L. 怎么走啊(最短路+二分 分段函数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

kotlin的函数forEach示例详解

《kotlin的函数forEach示例详解》在Kotlin中,forEach是一个高阶函数,用于遍历集合中的每个元素并对其执行指定的操作,它的核心特点是简洁、函数式,适用于需要遍历集合且无需返回值的场... 目录一、基本用法1️⃣ 遍历集合2️⃣ 遍历数组3️⃣ 遍历 Map二、与 for 循环的区别三、高

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

电脑开机提示krpt.dll丢失怎么解决? krpt.dll文件缺失的多种解决办法

《电脑开机提示krpt.dll丢失怎么解决?krpt.dll文件缺失的多种解决办法》krpt.dll是Windows操作系统中的一个动态链接库文件,它对于系统的正常运行起着重要的作用,本文将详细介绍... 在使用 Windows 操作系统的过程中,用户有时会遇到各种错误提示,其中“找不到 krpt.dll”

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

Linux搭建Mysql主从同步的教程

《Linux搭建Mysql主从同步的教程》:本文主要介绍Linux搭建Mysql主从同步的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux搭建mysql主从同步1.启动mysql服务2.修改Mysql主库配置文件/etc/my.cnf3.重启主库my

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链