分层图 的尝试学习 1.0
分层图:
分层图的最短路:
又叫做 扩点最短路。不把实际位置看做是图上的点,而是把实际位置及其状态的组合,(一个点有若干的状态,所以一个点会扩充出来若干点)看做是图上的点,然后搜索bfs或者dijkstra的过程不变。只是扩了点(分层)而已。
原理很简单,核心在于如何扩点,如何到达,如何算距离,每个题可能都不一样。注意计算扩充之后的点数。
添加链接描述
题意:
二维网格,只包含空房间,障碍,起点,钥匙和对应的锁(只有拿到对应的钥匙才能开对应的锁,否则锁的位置和障碍没什么区别,无法通过)问获得所有钥匙所需要移动的最小次数(相当于最短路),可以上下左右移动如果无法;获得所有的钥匙,返回-1
边长最多是30,钥匙最多是6
可以用一个数来代表这个点所获得的钥匙的状态。扩充后一共有30302^6 个点。57600个点。我感觉这道题的分层的感觉不是很强烈吧,感觉更多的是状态压缩。
使用三元组 (x,y,mask)表示当前状态。其中(x,y)代表当前所处的位置,mask 是一个二进制数,长度恰好等于网格中钥匙的数量,mask的第I个二进制位为1,当且仅当,我们已经获得了网格中的第i把钥匙。
之后使用广度优先搜索。
添加链接描述
题意:
对于一个有权无向图,可以将最多k条边 化为0,问从起点到终点的最短路。
分层图,可以看成有k+1 层图,代表了 使用0次,1次…k次 的图。
图和图之间 通过权值为0的边连接。
进行扩点,最多1e5个点。
使用二维的dis ,和vis 数组来标记状态。(其中一维代表了使用了几次的免费)
dij求 最短路 的时候,越晚确定 到原点最短路 的点,点 到原点的 距离越远。也就是说 根据 节点 确定dis 的顺序,dis 的数值 是不减 的。(毕竟后面的点 是前面点 松弛过来的,然后边权非负)
所以,扩点求最短路。最先遇到这个点 某个状态时,这个dis 是这个点所有状态里面的最短。
所以 在 dij ,如果遇到了终点,那么不管他的使用过的免费次数是多少,直接返回。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 10;
const int M = 5e5 + 10;
int h[M], to[M], ne[M];
int w[M];int tot = 1;
struct node
{int x;int k;// 使用了多少次的 免费机会int y;// 距离bool operator<(const node &a) const{return a.y < y;}
};
void add(int u, int v, int ww)
{to[tot] = v;ne[tot] = h[u];w[tot] = ww;h[u] = tot++;
}void solve()
{int n, m, k;cin >> n >> m >> k;vector<vector<int>> dis(n, vector<int>(k + 1, 1e9));vector<vector<int>> vis(n, vector<int>(k + 1, 0));int s, e;cin >> s >> e;int u, v, ww;while (m--){cin >> u >> v >> ww;add(u, v, ww);add(v, u, ww);}auto dij = [&](int s) -> void{dis[s][0] = 0;priority_queue<node> q;q.push({s,0,0});// 代表 点,使用免费的次数 ,距离while (!q.empty()){auto tt=q.top();int u=tt.x;int j=tt.k; int cost=tt.y;q.pop();if (vis[u][j])continue;vis[u][j] = 1;if (u==e){cout<<cost<<"\n";return; }for (int i = h[u]; i; i = ne[i]){int v = to[i];// 使用 免费 的机会if (j+1<=k&&dis[v][j+1]>dis[u][j]){dis[v][j+1]=dis[u][j];q.push({v,j+1,dis[v][j+1]});}// 不使用 免费 的机会 if (dis[v][j]>dis[u][j]+w[i]){dis[v][j]=dis[u][j]+w[i];q.push({v,j,dis[v][j]});}}}};dij(s);}
上面的那种思路,其实并没有真正的构建分层图,只是用了 增加了 一维的状态。去dp
下面是 构造分层图的代码
需要构建 k+1 层。每一层都有n 个节点
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x7fffffff
const int N = 2e5;//9e5
const int M =2e7;// 9e7
int h[N], to[M], ne[M];
int w[M], dis[N];
bool vis[N];
int tot = 1;
struct node
{int x;int y;bool operator<(const node &a) const{return a.y < y;}
};void add(int u, int v, int ww)
{to[tot] = v;ne[tot] = h[u];w[tot] = ww;h[u] = tot++;
}void dij(int s)
{fill(dis, dis + N, inf);dis[s] = 0;priority_queue<node> q;q.push({s, 0});while (!q.empty()){node u = q.top();q.pop();if (vis[u.x])continue;vis[u.x] = 1;for (int i = h[u.x]; i; i = ne[i]){int v = to[i];if (dis[v] > dis[u.x] + w[i]){dis[v] = dis[u.x] + w[i];q.push({v, dis[v]});}}}
}void solve()
{int n, m, k;cin >> n >> m >> k;int s, e;cin >> s >> e;int u, v;int ww;while (m--){// 读进来 一条边,将k+1 层,这条边都给建好cin >> u >> v >> ww;for (int j = 0; j <= k; j++){// 建 当前 层add(u+n*j, v+n*j, ww);add(v+n*j, u+n*j, ww);// 连接 这一层 和 下一层的 权值为 0的边(使用免费的票)if (j != k){add(u + n * j, v + n * (j + 1), 0);add(v + n * j, u + n * (j + 1), 0);}}}dij(s);int ans = inf;for (int j = e; j <= e+k * n; j += n)ans = min(ans, dis[j]);cout << ans << "\n";
}signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--)solve();return 0;
}相关文章:
分层图 的尝试学习 1.0
分层图: 分层图的最短路: 又叫做 扩点最短路。不把实际位置看做是图上的点,而是把实际位置及其状态的组合,(一个点有若干的状态,所以一个点会扩充出来若干点)看做是图上的点,然后搜索…...
第 31 章 javascript 之 XPath
第 31 章 XPath 1.IE 中的 XPath 2.W3C 中的 XPath 3.XPath 跨浏览器兼容 XPath 是一种节点查找手段,对比之前使用标准 DOM 去查找 XML 中的节点方式,大大降低了查找难度,方便开发者使用。但是,DOM3 级以前的标准并没有就 XPa…...
JavaScript中的高阶函数
高阶函数 所谓高阶函数,就是操作函数的函数,它接收一个或多个函数作为参数,并返回一个新函数: 来看一个mapper()函数,将一个数组映射到另一个使用这个函数的数组上: 更常见的例子,它接收两个函…...
Qt6.7开发安卓程序间接连接到MySQL的方法
本文主要描述一种通过间接的方法,使得Qt开发的安卓程序可以直连到Mysql数据库的方法。本文章的方案是通过JAVA代码去连接MySQL数据库,然后C代码去调用JAVA的方法,从而实现QT开发的安卓程序去直连到MySQL数据库。 本文使用 JDBC 结合 JNI&…...
ROW_NUMBER
How to rewrite a query which uses the ROW_NUMBER() window function in versions 5.7 or earlier before window functions were supported e.g., SELECT ROW_NUMBER() OVER (PARTITION BY fieldA) AS rownum, myTable.* FROM myTable; index 用不上的 Solution Assuming…...
Docker技术
目录 Docker的基本概念 Docker的核心原理 Docker的使用场景 Docker的优点 Docker的挑战 为什么使用 环境一致性 快速启动和部署 资源利用率高 支持微服务架构 持续集成与持续交付(CI/CD) 依赖管理 简化部署流程 高效资源管理 生态系统丰富…...
中小企业做网站需要考虑哪些因素?
中小企业在建设网站时,需要考虑的因素有很多。以下是一些主要考虑因素的介绍: 明确建站目的:中小企业需要明确自己建立网站的目的。是为了展示企业形象、推广产品,还是提供客户服务?不同的目的将决定网站的设计和功能…...
【d60】【Java】【力扣】509. 斐波那契数
思路 要做的问题:求F(n), F(n)就等于F(n-1)F(n-2),要把这个F(n-1)F(n-2)当作常量,已经得到的值, 结束条件:如果是第1 第2 个数字的时候,没有n-1和n-2,所以…...
项目-坦克大战学习-游戏结束
当boos受到伤害时游戏结束,游戏结束时我们需要将窗体全部绘制从别的画面,这样我们可以在游戏运行类中的update设置条件,在游戏运行类thread创建一个枚举类型定义是否游戏结束 public enum Game { play, over };//定义现在游戏运行状态 如果…...
MySQL基础之约束
MySQL基础之约束 概述 概念:约束是作用在字段的规则,限制表中数据 演示 # 多个约束之间不需要加逗号 # auto_increment 自增 create table user(id int primary key auto_increment comment 主键,name varchar(10) not null unique comment 姓名,age i…...
2024新版IDEA创建JSP项目
1. 创建项目 依次点击file->new->Project 配置如下信息并点击create创建项目 2. 配置Web项目 点击file->Project Structure 在点击Project Settings->Module右键右边模块名称->ADD->Web 点击Create Artifact 出现如下界面就表示配置完毕,…...
Conda创建,打包,删除环境相关及配置cuda
conda创建新环境Anaconda删除虚拟环境conda删除环境conda环境打包迁移及部署Python | Conda pack 进行环境打包Anaconda创建环境、删除环境、激活环境、退出环境Anaconda环境离线迁移_CondaPackError处理Anaconda环境离线迁移移植Anaconda-用conda创建python虚拟环境anaconda 配…...
Linux和指令初识
前言 Linux是我们在服务器中常用的操作系统,我们有必要对这个操作系统有足够的认识,并且能够使相关的指令操作。今天我们就来简单的认识一下这个操作的前世今生,并且介绍一些基础的指令操作 Linux的前世今生 要说Linux,还得从U…...
Vortex GPGPU的github流程跑通与功能模块波形探索(二)
文章目录 前言一、环境配置和debugging.md文档1.1 调试 Vortex GPU1.1.1测试 RTL 或模拟器 GPU 驱动的更改1.1.2 SimX 调试1.1.3 RTL 调试1.1.4 FPGA 调试1.1.5 分析 Vortex 跟踪日志 二、跑出波形文件和日志文件总结 前言 昨天另辟蹊径地去探索了子模块的波形仿真,…...
【X线源】微焦点X射线源的基本原理
【X线源】微焦点X射线源的基本原理 1.背景2.原理 1.背景 1895年11月8日,德国物理学家威廉伦琴在研究阴极射线时偶然发现了X射线。当时,他注意到阴极射线管附近的荧光屏发出了光,即使它被纸板遮挡住。经过进一步实验,他意识到这种…...
LeetCode hot100---栈专题(C++语言)
1、有效的括号 (1)题目描述以及输入输出 (1)题目描述: 给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串是否有效。(2)输入输出描述: 输入:s "()&…...
STM32-MPU6050+DAM库源码(江协笔记)
目录 1、MPU6050简介 2、MPU6050参数 3、MPU6050硬件电路 4、MPU6050结构 5、MPU6000和MPU6050的区别 6、MPU6050应用场景 7、MPU6050电气参数 8、MPU6050时钟源选择 9、MPU6050中断源 10、MPU6050的I2C读写操作 11、DMP库移植 1、MPU6050简介 10轴传感器࿱…...
Ruby 数组(Array)
Ruby 数组(Array) 引言 Ruby,作为一种高级编程语言,以其简洁明了的语法和强大的功能而闻名。在Ruby中,数组(Array)是一种基本的数据结构,用于存储一系列有序的元素。本文将深入探讨…...
分享几个做题网站------学习网------工具网;
以下是就是做题网站;趣IT官网-互联网求职刷题神器趣IT——互联网在线刷题学习平台,汇集互联网大厂面试真题,拥有java、C、Python、前端、产品经理、软件测试、新媒体运营等多个热门IT岗位面试笔试题库,提供能力测评、面试刷题、笔…...
Spring MVC__入门
目录 一、SpringMVC简介1、什么是MVC2、什么是SpringMVC 二、Spring MVC实现原理2.1核心组件2.2工作流程 三、helloworld1、开发环境2、创建maven工程3、配置web.xml4、创建请求控制器5、创建springMVC的配置文件6、测试HelloWorld7、总结 一、SpringMVC简介 1、什么是MVC MV…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
