E - Souvenir(图论典型例题)

思路:对于有很多询问的题,一般都是先初始化。我们求出每个点到其他点的最短路径以及相同路径下最大的价值和即可。
代码:
#include <bits/stdc++.h>
#define pb push_back
#define a first
#define b second
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef unsigned long long ull;char str[1005];
int main(){int n;scanf("%d",&n);vector <ll> A(n);for(int i=0;i<n;i++) scanf("%lld",&A[i]);vector < vector<int> > mp(n);for(int i=0;i<n;i++){scanf("%s",&str);mp[i].resize(n);for(int j=0;j<n;j++){mp[i][j]=str[j]=='Y';}mp[i][i]=1;}ll inf=1000000000000000;vector < vector<ll> > ans(n);vector < vector<int> > vd(n);for(int i=0;i<n;i++){ans[i].resize(n);for(int j=0;j<n;j++) ans[i][j]=-inf;vector <int> dist(n,n+1);queue <int> que;dist[i]=0;ans[i][i]=A[i];que.push(i);while(!que.empty()){int v=que.front();que.pop();for(int j=0;j<n;j++){if(mp[v][j]){if(dist[j]==n+1){dist[j]=dist[v]+1;que.push(j);}if(dist[j]==dist[v]+1){ans[i][j]=max(ans[i][j],ans[i][v]+A[j]);}}}}vd[i]=dist;}int Q;scanf("%d",&Q);for(int i=0;i<Q;i++){int u,v;scanf("%d%d",&u,&v);u--,v--;if(ans[u][v]==-inf) puts("Impossible");else printf("%d %lld\n",vd[u][v],ans[u][v]);}
}
相关文章:
E - Souvenir(图论典型例题)
思路:对于有很多询问的题,一般都是先初始化。我们求出每个点到其他点的最短路径以及相同路径下最大的价值和即可。 代码: #include <bits/stdc.h> #define pb push_back #define a first #define b second using namespace std; type…...
【SpringBoot篇】添加富文本编辑器操作
文章目录 🍔使用步骤⭐首先我们需要安装富文本编辑器⭐在<script>中引入富文本编辑器⭐富文本图片上传接口⭐初始化富文本编辑器⭐调用 初始化富文本编辑器的方法🎈新增🎈编辑🎈保存 ⭐添加按钮⭐实现viewEditor函数&#x…...
前台vue配置
前台 vue环境 1.傻瓜式安装node: 官网下载:https://nodejs.org/zh-cn/2.安装cnpm: >: npm install -g cnpm --registryhttps://registry.npm.taobao.org3.安装vue最新脚手架: >: cnpm install -g vue/cli注:如果2、3步报错,清除缓…...
牛客周赛 Round 18 解题报告 | 珂学家 | 分类讨论计数 + 状态DP
前言 整体评价 前三题蛮简单的,T4是一个带状态的DP,这题如果用背包思路去解,不知道如何搞,感觉有点头痛。所以最后还是选择状态DP来求解。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 游游的整数翻转 这题最好…...
CentOS防火墙基本操作
CentOS操作系统中的防火墙可以使用firewalld或iptables来进行配置。 firewalld(默认): 查看当前状态:systemctl status firewalld 开启/关闭防火墙服务:sudo systemctl start/stop firewalld 设置开机自动启动/不启…...
Shell脚本的编程规范和变量类型
一. 了解编程 1.程序编程风格 面向过程语言 开发的时候 需要一步一步执行 问题规模小,可以步骤化,按部就班处理 以指令为中心,数据服务于指令 C,shell 面向对象语言 开发的时候 将任务当成一个整体 将编程看成是一个…...
C++面试:跳表
目录 跳表介绍 跳表的特点: 跳表的应用场景: C 代码示例: 跳表的特性 跳表示例 总结 跳表(Skip List)是一种支持快速搜索、插入和删除的数据结构,具有相对简单的实现和较高的查询性能。下面是跳表…...
掌握C++20的革命性特性:Concepts
掌握C20的革命性特性:Concepts C20 的新特性 C20 引入了 Concepts,这是一种用于限制类和函数模板的模板类型和非类型参数的命名要求。Concepts 是作为编译时评估的谓词,用于验证传递给模板的模板参数。Concepts 的主要目的是使模板相关的编…...
win11开机后频繁刷新桌面,任务栏不显示,文件资源管理器explorer报错ntdll.dll
win11 开机后桌面频繁刷新,cpu 暴涨,任务栏不出现。 不知道是安装了什么软件还是系统升级造成的,好长时间不重启电脑了,然后重启了下电脑。 结果就是: 现象描述 重启后 输入密码进入后 变得巨慢。好久才进入的桌面。…...
解决Git添加.gitignore文件后不生效的问题
1. 问题描述 如上图所示,在已存在.gitignore文件且已经提交过的Git管理的项目中,其中.class、.jar文件以及.idea目录内的内容全部都还是被Git管理了,可见.gitignore文件并没有生效。 2. 原因发现 .gitignore文件只能作用于 Untracked Files…...
Shell Linux学习笔记
注意:该文章摘抄之百度,仅当做学习笔记供小白使用,若侵权请联系删除! 目录 什么是shell ? Linux正则匹配 grep tar与unzip echo history 重定向 shell 单双引号 位置参数 预定义变量 运算 正则表达式 字符截取命令 …...
kingbase常用SQL总结之锁等待信息
锁信息与等待事件 分析kingbase(pg)数据库锁等待、死锁时需要我们准确的定位等锁或者死锁相关的事务。关于获取锁等待信息或者死锁信息已有经典的SQL可以直接使用,但是需要我们先了解sql语句获取的每个字段的意义。 获取到锁等待事务不能完全…...
「优选算法刷题」:长度最小的子数组
一、题目 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输…...
RuoYi-Cloud本地部署--详细教程
文章目录 1、gitee项目地址2、RuoYi-Cloud架构3、本地部署3.1 下载项目3.2 idea打开项目3.3 启动nacos3.4 若依数据库准备3.5 启动redis3.6 修改nacos中的各个模块的配置文件3.7 启动ruoyi前端项目3.8 启动各个微服务模块 4、启动成功 1、gitee项目地址 https://gitee.com/y_p…...
如何优雅的发布一个 TypeScript 软件包?
向 NPM 发布软件包本身并不是一个特别困难的挑战。但是,配置你的 TypeScript 项目以取得成功可能是一个挑战。你的软件包能在大多数项目上运行吗?用户能否使用类型提示和自动完成功能?它能与 ES Modules (ESM) 和 CommonJS (CJS) 风格的导入一…...
总结的太到位:python 多线程系列详解
前言: 上vip课的时候每次讲到框架的执行,就会有好学的同学问用多线程怎么执行,然后我每次都会说在测开课程会详细讲解,这并不是套路,因为如果你不理解多线程,不清楚什么时候该用什么时候不该用,…...
惬意上手Python —— 装饰器和内置函数
1. Python装饰器 Python中的装饰器是一种特殊类型的函数,它允许用户在不修改原函数代码的情况下,增加或修改函数的行为。 具体来说,装饰器的工作原理基于Python的函数也是对象这一事实,可以被赋值给变量、作为参数传递给其他函数或者作为其他…...
python 调用dll
在Python中,可以使用ctypes库来调用DLL文件。ctypes库是一个标准库,用于在Python中加载共享库(例如DLL文件)并调用其中的函数。 以下是一个简单的示例,演示如何使用ctypes库调用DLL文件中的函数: import c…...
docker里Java服务执行ping命令模拟流式输出
文章目录 业务场景处理解决实现ping功能并实时返回输出实现长ping和中断请求docker容器找不到ping命令处理 业务场景 我们某市的客户,一直使用CS版本的信控平台,直接安装客户Windows server服务器上,主要对信号机设备进行在线管理、方案配时…...
代码随想录算法训练营第十三天| 239. 滑动窗口最大值 、347.前 K 个高频元素
239. 滑动窗口最大值 思路: 用遍历区间的元素时,维护一个单调队列,从大到小排列。 要找到最大值,实际单调队列保存区间内最大值及最大值右侧的第二大值(用于当前最大值处于区间左端,在区间右移时更新临时最…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
