当前位置: 首页 > news >正文

POJ3037 + HDU-6714

两道最短路好题

POJ3037

手玩一下 发现每一点的速度可以直接搞出来,就是pow(2,h[1][1]-h[i][j])*V

那么从这个点出发到达别的点的耗费的时间都是上面这个数的倒数,然后直接跑最短路就好了

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}int n,q,m,v;
bool vis[1010][1010];
// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){// e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
// }double vs[1010][1010];
double dist[1010][1010];
double h[1010][1010];void solve()
{cin>>v>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){double x;cin>>x;h[i][j] = x;vs[i][j] = pow(2,x-h[1][1])/v; dist[i][j] = 1e15;}}dist[1][1] = 0;queue<pair<int,int>>q;q.push(make_pair(1,1));int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};vis[1][1] = true;while(q.size()){pair<int,int> t = q.front();q.pop();int x = t.first,y = t.second;vis[x][y] = false;//cout<<x<<" "<<y<<"\n";for(int i=0;i<4;i++){int temx = x+dx[i],temy = y+dy[i];if(temx<1||temx>n||temy<1||temy>m)continue;//cout<<temx<<" "<<temy<<"\n";if(dist[temx][temy]>dist[x][y]+vs[x][y]){dist[temx][temy] = dist[x][y]+vs[x][y];if(!vis[temx][temy]){vis[temx][temy] = true;q.push(make_pair(temx,temy));}}}}printf("%.2lf",dist[n][m]);}signed main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;//cin>>_;_ = 1;while(_--)solve();return 0;
}

HDU6714

这个dijk记数还是很有意思的,你得明白folyd的含义但是别被DP的含义绕进去

每次暴力的跑每一个点的单源最短路,然后当有中间点的时候你就更新一下就行了,没有中间的时候D【i】【j】就是一开始的距离,没有被更新,还是很有趣的,还是得想明白floyd的具体过程(好像不懂也行

一开始我就被绕进去了,一直在扣floyd 的含义来写这道,发现直接按上面的做法就好了

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
using pii = pair<int,int>;
const int N = 1e4+10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int gcd(int a,int b){return b?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}int n,q,m;
int id[N];
int e[N],ne[N],w[N],h[N],idx;
void add(int a,int b,int c){e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}bool vis[N];
ll dist[N];void dijkstra(int mid)
{memset(dist,0x3f,sizeof dist);memset(vis,0,sizeof vis);memset(id,0,sizeof id);priority_queue<pii,vector<pii>,greater<pii>>heap;heap.push({0,mid});dist[mid] = 0;while(heap.size()){auto t = heap.top();heap.pop();int ver = t.second;if(vis[ver])continue;vis[ver] = true;//cout<<ver<<"\n";for(int i=h[ver];~i;i=ne[i]){int j = e[i];if(dist[j]>dist[ver]+w[i]){dist[j] = dist[ver]+w[i];heap.push({dist[j],j});if(ver==mid)continue;id[j] = max(id[ver],ver);}else if(dist[j]==dist[ver]+w[i]){id[j] = min(id[j],max(id[ver],ver));}}}
}void solve()
{cin>>n>>m;memset(h,-1,sizeof h);idx = 0;while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}int ans = 0;for(int i=1;i<=n;i++){dijkstra(i);for(int j=1;j<=n;j++)ans = (id[j]+ans)%mod;//cout<<"\n";}cout<<ans;}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;cin>>_;//_ = 1;while(_--)solve();return 0;
}

相关文章:

POJ3037 + HDU-6714

两道最短路好题 POJ3037 手玩一下 发现每一点的速度可以直接搞出来&#xff0c;就是pow(2,h[1][1]-h[i][j])*V 那么从这个点出发到达别的点的耗费的时间都是上面这个数的倒数&#xff0c;然后直接跑最短路就好了 #include<iostream> #include<vector> #include<…...

Ubuntu搭建环境Cmake-Libtorch-Torchvision-PCL-VTK-OpenCV

Ubuntu搭建环境Cmake-Libtorch-Torchvision-PCL-VTK-OpenCV 安装Cmake安装libtorch安装torchvision安装PCL安装VTK安装OpenCV设置环境变量 仅供本人记录查阅使用 安装Cmake Cmake下载地址 解压 进入目录会看到只有 bin doc man share三个文件夹&#xff0c;没有 bootstrap文…...

分享多种mfc100u.dll丢失的解决方法(一键修复DLL丢失的方法)

在使用电脑过程中&#xff0c;我们经常会遇到一些陌生的DLL文件&#xff0c;例如mfc100u.dll。这些DLL文件是动态链接库&#xff08;Dynamic Link Libraries&#xff09;的缩写&#xff0c;它们包含了可以被多个程序共享的代码和数据。今天&#xff0c;我们将深入探讨mfc100u.d…...

Redis是单线程还是多线程?(面试题)

1、Redis5及之前是单线程版本 2、Redis6开始引入多线程版本&#xff08;实际上是 单线程多线程 版本&#xff09; Redis6及之前版本&#xff08;单线程&#xff09; Redis5及之前的版本使用的是 单线程&#xff0c;也就是说只有一个 worker队列&#xff0c;所有的读写操作都要…...

动态菜单设计

需求&#xff1a; 登录不同用户 显示不同的菜单 思路&#xff1a;根据用户id 左关联表 查询出对应的菜单选项 查询SQL select distinct-- 菜单表 去除重复记录sys_menu.id,sys_menu.parentId, sys_menu.name from -- 权限表sys_menu-- 角色与权限表 菜单表id 角色菜…...

Haproxy负载均衡介绍即部署

haproxy的原理&#xff1a; 提供高可用、负载均衡以及基于TCP&#xff08;四层&#xff09;和HTTP&#xff08;七层&#xff09;应用的代理&#xff0c;支持虚拟主机&#xff0c;开源可靠的一款软件。 适用于哪些负载特别大的web站点&#xff0c;这些站点通常又需要回话保持和七…...

基于大语言模型的云故障根因分析|顶会EuroSys24论文

*马明华 微软主管研究员 2021年CCF国际AIOps挑战赛程序委员会主席&#xff08;第四届&#xff09; 2021年博士毕业于清华大学&#xff0c;2020年在佐治亚理工学院做访问学者。主要研究方向是智能运维&#xff08;AIOps&#xff09;、软件可靠性。近年来在ICSE、FSE、ATC、EuroS…...

Windows直接运行python程序

Windows直接运行python程序 一、新建bat脚本二、新建vbs脚本 一、新建bat脚本 新建bat批处理脚本&#xff0c;写入以下内容 echo off call conda activate pytorch python app.pyecho off&#xff1a;在此语句后所有运行的命令都不显示命令行本身&#xff0c;但是本身的指令是…...

经典应用丨光伏行业扫码追溯新标杆,海康机器人AI智能读码器!

去年&#xff0c;光伏发电行业持续高速发展&#xff0c;我国仅在前九个月累计装机521.08GW&#xff0c;同比增长达到45.3%&#xff0c;已成为第二大电源类型超过水电。根据《2023中国与全球光伏发展白皮书》预测&#xff0c;到2030年&#xff0c;中国能够实现国家规划的风电和光…...

逆流而上的选择-积极生活,逆流而上

首先请大家看一个故事 李明坐在公司的开放式办公区&#xff0c;耳边是键盘敲击声的交响乐&#xff0c;眼前是一行行跳跃的代码。他的眼神有些恍惚&#xff0c;显示器的蓝光在他眼镜上反射出时代的光芒&#xff0c;这光芒既耀眼又刺眼。他即将35岁&#xff0c;在这个年纪&#x…...

SpringMVC基础Controller

文章目录 Controller 的编写和配置1. Controller 注解类型2. RequestMapping 注解类型3. 编写请求方法4. 请求参数和路径变量 Controller 的编写和配置 Controller 注解和 RequestMapping 注解是 Spring MVC 最重要的两个注解。 使用基于注解的控制器的优点如下&#xff1a; …...

spark 参数

spark.yarn.executor.memoryOverhead 默认值是384M Configuration - Spark 3.5.1 Documentation...

java调用jacob进行文件转换ppt转pdf或者png

java调用jacob进行文件转换ppt转pdf或者png 前情提要 最近项目上&#xff0c;遇到一个复杂的ppt&#xff0c;最终要求是要将ppt每一页转成图片原本这个是不难&#xff0c;网上一搜一大堆案例&#xff0c;外加我本身也比较精通aspose&#xff0c;那还不是分分钟搞定。结果就是…...

鸿蒙HarmonyOS应用开发之使用DevEco Studio模板构建NDK工程

NDK通过CMake和Ninja编译应用的C/C代码&#xff0c;编译过程如下图所示。 核心编译过程如下&#xff1a; 根据CMake配置脚本以及build-profile.json5中配置的externalNativeOptions构建参数&#xff0c;与缓存中的配置比对后&#xff0c;生成CMake命令并执行CMake。 执行Ninja…...

uniapp流浪动物救助小程序Java宠物领养小程序springboot

uniapp流浪动物救助小程序Java宠物领养小程序springboot 代码40块&#xff0c;需要的私聊 前台基于uniapp小程序 后台管理基于springbootvue前后端分离项目 开发语言&#xff1a;Java 框架&#xff1a;springboot vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xf…...

工程企业的未来选择:Java版工程项目管理系统平台与数字化管理的融合

在现代化的工程项目管理中&#xff0c;一套功能全面、操作便捷的系统至关重要。本文将介绍一个基于Spring Cloud和Spring Boot技术的Java版工程项目管理系统&#xff0c;结合Vue和ElementUI实现前后端分离。该系统涵盖了项目管理、合同管理、预警管理、竣工管理、质量管理等多个…...

Vue使用el-statistic和el-card显示大屏中的统计数据

​ 一、页面内容&#xff1a; <el-row :gutter"20"><el-col :span"6"><el-card class"box-card"><div><el-statisticgroup-separator",":precision"2":value"value2":title"tit…...

12.2024

如下图所示&#xff0c;小明用从1开始的正整数“蛇形”填充无限大的矩阵。 1 2 6 7 15 16 28 29... 35 8 14 17 27 30... 4 9 13 18 26 31... 10 12 19 25 32... 11 20 24 33... 21 23 34.. 22 35... 容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20行第20列的数是多少…...

【学习心得】Jupyter常用操作与魔法方法

一、安装与打开 Jupyter是什么我就不啰嗦了&#xff0c;直接安装&#xff1a; pip install jupyter 安装完后&#xff0c;在你想要打开的项目路径下&#xff0c;唤出CMD执行下面命令就可以使用jupyter notebook了 jupyter notebook 也可以用更加好用的jupyter lab&#xff0…...

Linux命令别名

别名是命令的快捷方式。对于需要经常执行&#xff0c;并需要很长时间输入的长命令创建快捷方式很有用。 临时修改 语法&#xff1a; alias 别名原命令 [选项] [参数][rootdd ~]# alias cdtcd /test #切换到/test下的快捷命令 删除别名&#xff1a; unalias 别名 unalias cd…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

ubuntu中安装conda的后遗症

缘由: 在编译rk3588的sdk时&#xff0c;遇到编译buildroot失败&#xff0c;提示如下&#xff1a; 提示缺失expect&#xff0c;但是实测相关工具是在的&#xff0c;如下显示&#xff1a; 然后查找借助各个ai工具&#xff0c;重新安装相关的工具&#xff0c;依然无解。 解决&am…...

Docker环境下安装 Elasticsearch + IK 分词器 + Pinyin插件 + Kibana(适配7.10.1)

做RAG自己打算使用esmilvus自己开发一个&#xff0c;安装时好像网上没有比较新的安装方法&#xff0c;然后找了个旧的方法对应试试&#xff1a; &#x1f680; 本文将手把手教你在 Docker 环境中部署 Elasticsearch 7.10.1 IK分词器 拼音插件 Kibana&#xff0c;适配中文搜索…...

轻量安全的密码管理工具Vaultwarden

一、Vaultwarden概述 Vaultwarden主要作用是提供一个自托管的密码管理器服务。它是Bitwarden密码管理器的第三方轻量版&#xff0c;由国外开发者在Bitwarden的基础上&#xff0c;采用Rust语言重写而成。 &#xff08;一&#xff09;Vaultwarden镜像的作用及特点 轻量级与高性…...