Rinne Loves Graph
Rinne Loves Graph (nowcoder.com)
链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
题目描述
Island 发生了一场暴乱!现在 Rinne 要和 Setsuna 立马到地上世界去。
众所周知:Island 是有一些奇怪的城镇和道路构成的(题目需要,游戏党勿喷),有些城镇之间用双向道路连接起来了,且每条道路有它自己的距离。但是有一些城镇已经被派兵戒严,虽然主角可以逆天改命强闯,但是为了体验该游戏的平衡性,他们只能穿过不超过 K 次被戒严的城镇。
定义“穿过”:从一个戒严的点出发到达任意一个点,都会使得次数加1
现在他们想从 1 号城镇最快的走到 n 号城镇(即出口),现在他们想让你告诉他们最短需要走多少路。
输入描述:
第一行三个整数 n,m,k,分别表示城镇数量,边数量和最多能闯过被戒严的城市的次数。 接下来 n 行,每行一个整数 1 或 0,如果为 1 则表示该城市已被戒严,0 则表示相反。 接下来 m 行,每行三个数 u,v,w,表示在 u 城镇和 v 城镇之间有一条长度为 w 的双向道路。
输出描述:
输出一行一个数字,表示从 1 到 n 的最短路径,如果到达不了的话,请输出 -1。
示例1
输入
复制4 5 1 1 0 1 0 1 2 10 2 3 10 3 1 15 1 4 60 3 4 30
4 5 1 1 0 1 0 1 2 10 2 3 10 3 1 15 1 4 60 3 4 30
输出
复制60
60
先上WA的代码(90%通过率)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 810;
vector<int>defense(maxn), dis(maxn, INT_MAX), pre(maxn, -1), vis(maxn);
#define endl '\n'
int n, m, k, A, B, len;
struct edge
{int form, to, dis;edge(int a, int b, int c) : form(a), to(b), dis(c) {};
};
vector<edge>e[maxn];
struct q_node
{int id, dis;q_node(int a, int b) : id(a), dis(b) {};bool operator < (const q_node& s)const{return dis > s.dis;}
};
void dijkstra()
{dis[1] = 0;int T = 0;// defense[1];priority_queue<q_node>Q;Q.emplace(1, dis[1]);while (!Q.empty()){auto x = Q.top();Q.pop();if (T == k && defense[x.id] == 1)vis[x.id] = true;if (vis[x.id])continue;vis[x.id] = true;T += defense[x.id];for (int i = 0; i < e[x.id].size(); i++){auto y = e[x.id][i];// if (T == k && defense[y.to] == 1 && y.to != n)vis[y.to] = true;if (vis[y.to])continue;if (dis[y.to] > dis[x.id] + y.dis){dis[y.to] = dis[x.id] + y.dis;pre[y.to] = x.id;Q.emplace(y.to, dis[y.to]);}}}
}
int main()
{cin.tie(0)->sync_with_stdio(false);cin >> n >> m >> k;for (int i = 1; i <= n; i++)cin >> defense[i];while (m--){cin >> A >> B >> len;e[A].emplace_back(A, B, len);e[B].emplace_back(B, A, len);}dijkstra();dis[n] == INT_MAX ? cout << "-1" << endl : cout << dis[n] << endl;return 0;
}
进行更改后通过的代码
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn = 810;
vector<int>defense(maxn), dis(maxn, INT_MAX), pre(maxn, -1), vis(maxn);
#define endl '\n'
int n, m, k, A, B, len;
struct edge
{int form, to, dis;edge(int a, int b, int c) : form(a), to(b), dis(c) {};
};
vector<edge>e[maxn];
struct q_node
{int id, dis, T;q_node(int a, int b, int c) : id(a), dis(b), T(c) {};bool operator < (const q_node& s)const{return dis > s.dis;}
};
void dijkstra()
{dis[1] = 0;priority_queue<q_node>Q;Q.emplace(1, dis[1], defense[1]);if(!k && defense[1])return;while (!Q.empty()){auto x = Q.top();Q.pop();if (vis[x.id])continue;vis[x.id] = true;for (int i = 0; i < e[x.id].size(); i++){auto y = e[x.id][i];if (vis[y.to])continue;if (dis[y.to] > dis[x.id] + y.dis && (x.T + defense[y.to] <= k || y.to == n)){dis[y.to] = dis[x.id] + y.dis;pre[y.to] = x.id;//defense[y.to] += x.T; Q.emplace(y.to, dis[y.to], x.T + defense[y.to]);}}}
}
int main()
{cin.tie(0)->sync_with_stdio(false);cin >> n >> m >> k;for (int i = 1; i <= n; i++)cin >> defense[i];while (m--){cin >> A >> B >> len;e[A].emplace_back(A, B, len);e[B].emplace_back(B, A, len);}dijkstra();dis[n] == INT_MAX ? cout << "-1" << endl : cout << dis[n] << endl;return 0;
}
首先对于结构体的解释
struct q_node
{int id, dis, T;q_node(int a, int b, int c) : id(a), dis(b), T(c) {};bool operator < (const q_node& s)const{return dis > s.dis;}
};
id是城镇编号,dis为使用这条边将id纳入最短路花费的距离,T表示使用这条边要战斗的次数
其中 defense[y.to] += x.T; 一定不能使用(对于这题而言如果更改defense只能通过90%原因后面解释)
defense用于记录该城镇是否有敌人防御
为什么defense不能更改反而要在结构体中新添一个变量T ?
原因:每一个点可能会经过多次松弛,可能对于该次松弛,该点无法纳入最短路,如果我们这时候将defense进行更改相当于直接否认该点能纳入最短路,但是可能在后面的松弛中该点又被允许纳入选择中.因此对于同一个点,起点到该的需要战斗的次数受之前的选择决定,每一次对于战斗的状态的不固定的,那我们就得根据边的选择来记录当前到该城镇所需战斗的状态
相关文章:
Rinne Loves Graph
Rinne Loves Graph (nowcoder.com) 链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 题目描述 Island 发生了一场暴乱!现在 Rinne 要和 Setsuna 立马到地上世界去。 众所周知:Island 是有一些奇怪的城镇和道路构成的…...
第15章:索引的数据结构
一、为什么使用索引 1.索引是存储引擎用于快速找到记录的一种数据结构。相当于一本书的目录。在进行数据查找时,首先查看查询条件是否命中某条索引,符合则通过索引查找相关数据。如果不符合则需要全表扫描,一条一条查找记录,直到…...
机械师曙光16电脑开机自动蓝屏怎么解决?
机械师曙光16电脑开机自动蓝屏怎么解决?有的用户在使用机械师曙光16电脑的时候,遇到了一些系统问题,导致自己无法正常的开机使用电脑。因为电脑总会变成蓝屏,无法进行任何操作。那么这个情况怎么去进行问题的解决呢?来…...
机器学习_Lasso回归_ElasticNet回归_PolynomialFeatures算法介绍_02---人工智能工作笔记0037
Lasso回归用的是L1正则化可以看到,这里的alpha就是这里的alpha对吧,就是 L1的权重 然后对于ElasticNet回归来说,这里的alpha可以看到是L1权重的超参数对吧,然后这里的p,表示的是 L2正则里面的(1-p)这里 这里要提一下: L1和L2为什么能防止过拟合,它们有什么区别?通过添加…...
第五篇:强化学习基础之马尔科夫决策过程
你好,我是zhenguo(郭震) 今天总结强化学习第五篇:马尔科夫决策过程 基础 马尔科夫决策过程(MDP)是强化学习的基础之一。下面统一称为:MDP MDP提供了描述序贯决策问题的数学框架。 它将决策问题建模为: 状态…...
Oracle面试题
1. 什么是存储过程,使用存储过程的好处? 存储过程(Stored Procedure )是一组为了完成特定功能的SQL 语句集,经编译后存储在数据库中。用户通过指定存储过程的名字并给出参数(如果该存储过程带有参数&#…...
用Vue写教务系统学生管理
文章目录 一.首先创建新的Demo二.在APP里面绑定DemoStudent三.源码附上四.效果图(新增记录还未实现) 一.首先创建新的Demo 二.在APP里面绑定DemoStudent <template><img alt"Vue logo" src"./assets/logo.png"><!--…...
专门用于管理企业与自己客户之间所有信息的客户管理系统
一、开源项目简介 关于 NXCRM NXCRM 是一套基于 Laravel 的 CRM 应用程序。它包含了一个管理中心,可以管理用户、客户、产品、订单、商机,合同,收款,附件,联系人,跟进动态,发票,业…...
(转载)基于多层编码遗传算法的车间调度算法(matlab实现)
以下内容大部分来源于《MATLAB智能算法30个案例分析》,仅为学习交流所用。 1 理论基础 遗传算法具有较强的问题求解能力,能够解决非线性优化问题。遗传算法中的每个染色体表示问题中的一个潜在最优解,对于简单的问题来说,染色体…...
Redis的常用数据结构之哈希类型
首先这里说的哈希类型针对的是redis中的value的k-v结构 常见的操作命令 hset设置值 hsetnx命令,不存在可以设置,存在设置不成功 hget取值,这里与字符串类型不同是要精确到filed。前面的判断也是基于field来实现的 要是field没有就返回null h…...
计算机组成原理-存储系统-缓存存储器(Cache)
目录 一、Cache基本概念 1.2性能分析 二、 Cache和主存的映射发生 2.1全相连映射编辑 2.2直接映射编辑 2.3组相连映射 三、Cachae的替换算法 3.1 随机算法(RADN) 3.2 先进先出算法(FIFO) 3.3 近期最少使用(LRU) 3.4 最近不经常使用(LFU) 四、写策略 4…...
打开c语言生成exe文件,出现闪退的解决方法
为什么打开c语言生成的exe文件,立马闪退。 起初个别问的时候,我只是简单的说明程序运行完了,就自动关了, 首先,生成的exe文件本质是控制台程序,这些都是依赖于windows的控制台窗口,程序执行完…...
算法基础学习笔记——⑩DFS与BFS\树与图
✨博主:命运之光 ✨专栏:算法基础学习 目录 DFS与BFS\树与图 ✨DFS ✨BFS 🍓宽搜流程图如下: 🍓宽搜流程: 🍓广搜模板 ✨树与图 🍓树是特殊的图(连通无环的图&am…...
chatgpt赋能python:Python中可迭代对象的介绍
Python中可迭代对象的介绍 Python是一种高级编程语言,它具有简单易学、可读性强、功能强大等特点,成为了数据科学、机器学习、Web开发等领域的热门选择。Python中有很多重要的概念和功能,其中之一就是支持可迭代对象的概念。 在Python中&am…...
报表控件FastReport使用指南——如何打开WebP格式的图片
FastReport 是功能齐全的报表控件,可以帮助开发者可以快速并高效地为.NET,VCL,COM,ActiveX应用程序添加报表支持,由于其独特的编程原则,现在已经成为了Delphi平台最优秀的报表控件,支持将编程开…...
【鲁棒、状态估计】用于电力系统动态状态估计的鲁棒迭代扩展卡尔曼滤波器研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
整理6个超好用的在线编辑器!
随着 Web 开发对图像可扩展性、响应性、交互性和可编程性的需求增加,SVG 图形成为最适合 Web 开发的图像格式之一。它因文件小、可压缩性强并且无论如何放大或缩小,图像都不会失真而受到欢迎。然而,为了编辑 SVG 图像,需要使用 SV…...
ArcGIS10.8下载及安装教程(附安装步骤)
谷歌云: https://drive.google.com/drive/folders/10igu7ZSMaR0v0WD7-2W-7ADJGMUFc2ze?uspsharing ArcGIS10.8 百度网盘: https://pan.baidu.com/s/1s5bL3QsCP5sgcftCPxc88w 提取码:kw4j 阿里云: https://www.aliyundriv…...
AI智能照片编辑:AI Photo for Mac
AI Photo是一款Mac平台上的智能照片编辑软件,它基于人工智能技术,可以帮助用户快速、轻松地对照片进行编辑和美化。AI Photo提供了多种智能修复和美化功能,包括自动调整色彩、对比度、亮度、清晰度等,使得照片的质量得到有效提升。…...
Tuxera for Mac2023中文版读写硬盘U盘工具
在日常生活中,我们使用Mac时经常会遇到外部设备不能正常使用的情况,如:U盘、硬盘、软盘等等一系列存储设备,而这些设备的格式大多为NTFS,Mac系统对NTFS格式分区存在一定的兼容性问题,不能正常读写。 那么什…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
