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

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(图论典型例题)

思路&#xff1a;对于有很多询问的题&#xff0c;一般都是先初始化。我们求出每个点到其他点的最短路径以及相同路径下最大的价值和即可。 代码&#xff1a; #include <bits/stdc.h> #define pb push_back #define a first #define b second using namespace std; type…...

【SpringBoot篇】添加富文本编辑器操作

文章目录 &#x1f354;使用步骤⭐首先我们需要安装富文本编辑器⭐在<script>中引入富文本编辑器⭐富文本图片上传接口⭐初始化富文本编辑器⭐调用 初始化富文本编辑器的方法&#x1f388;新增&#x1f388;编辑&#x1f388;保存 ⭐添加按钮⭐实现viewEditor函数&#x…...

前台vue配置

前台 vue环境 1.傻瓜式安装node: 官网下载&#xff1a;https://nodejs.org/zh-cn/2.安装cnpm: >: npm install -g cnpm --registryhttps://registry.npm.taobao.org3.安装vue最新脚手架: >: cnpm install -g vue/cli注&#xff1a;如果2、3步报错&#xff0c;清除缓…...

牛客周赛 Round 18 解题报告 | 珂学家 | 分类讨论计数 + 状态DP

前言 整体评价 前三题蛮简单的&#xff0c;T4是一个带状态的DP&#xff0c;这题如果用背包思路去解&#xff0c;不知道如何搞&#xff0c;感觉有点头痛。所以最后还是选择状态DP来求解。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 游游的整数翻转 这题最好…...

CentOS防火墙基本操作

CentOS操作系统中的防火墙可以使用firewalld或iptables来进行配置。 firewalld&#xff08;默认&#xff09;&#xff1a; 查看当前状态&#xff1a;systemctl status firewalld 开启/关闭防火墙服务&#xff1a;sudo systemctl start/stop firewalld 设置开机自动启动/不启…...

Shell脚本的编程规范和变量类型

一. 了解编程 1.程序编程风格 面向过程语言 开发的时候 需要一步一步执行 问题规模小&#xff0c;可以步骤化&#xff0c;按部就班处理 以指令为中心&#xff0c;数据服务于指令 C&#xff0c;shell 面向对象语言 开发的时候 将任务当成一个整体 将编程看成是一个…...

C++面试:跳表

目录 跳表介绍 跳表的特点&#xff1a; 跳表的应用场景&#xff1a; C 代码示例&#xff1a; 跳表的特性 跳表示例 总结 跳表&#xff08;Skip List&#xff09;是一种支持快速搜索、插入和删除的数据结构&#xff0c;具有相对简单的实现和较高的查询性能。下面是跳表…...

掌握C++20的革命性特性:Concepts

掌握C20的革命性特性&#xff1a;Concepts C20 的新特性 C20 引入了 Concepts&#xff0c;这是一种用于限制类和函数模板的模板类型和非类型参数的命名要求。Concepts 是作为编译时评估的谓词&#xff0c;用于验证传递给模板的模板参数。Concepts 的主要目的是使模板相关的编…...

win11开机后频繁刷新桌面,任务栏不显示,文件资源管理器explorer报错ntdll.dll

win11 开机后桌面频繁刷新&#xff0c;cpu 暴涨&#xff0c;任务栏不出现。 不知道是安装了什么软件还是系统升级造成的&#xff0c;好长时间不重启电脑了&#xff0c;然后重启了下电脑。 结果就是&#xff1a; 现象描述 重启后 输入密码进入后 变得巨慢。好久才进入的桌面。…...

解决Git添加.gitignore文件后不生效的问题

1. 问题描述 如上图所示&#xff0c;在已存在.gitignore文件且已经提交过的Git管理的项目中&#xff0c;其中.class、.jar文件以及.idea目录内的内容全部都还是被Git管理了&#xff0c;可见.gitignore文件并没有生效。 2. 原因发现 .gitignore文件只能作用于 Untracked Files…...

Shell Linux学习笔记

注意&#xff1a;该文章摘抄之百度&#xff0c;仅当做学习笔记供小白使用&#xff0c;若侵权请联系删除&#xff01; 目录 什么是shell ? Linux正则匹配 grep tar与unzip echo history 重定向 shell 单双引号 位置参数 预定义变量 运算 正则表达式 字符截取命令 …...

kingbase常用SQL总结之锁等待信息

锁信息与等待事件 分析kingbase&#xff08;pg&#xff09;数据库锁等待、死锁时需要我们准确的定位等锁或者死锁相关的事务。关于获取锁等待信息或者死锁信息已有经典的SQL可以直接使用&#xff0c;但是需要我们先了解sql语句获取的每个字段的意义。 获取到锁等待事务不能完全…...

「优选算法刷题」:长度最小的子数组

一、题目 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0 。 示例 1&#xff1a; 输…...

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 发布软件包本身并不是一个特别困难的挑战。但是&#xff0c;配置你的 TypeScript 项目以取得成功可能是一个挑战。你的软件包能在大多数项目上运行吗&#xff1f;用户能否使用类型提示和自动完成功能&#xff1f;它能与 ES Modules (ESM) 和 CommonJS (CJS) 风格的导入一…...

总结的太到位:python 多线程系列详解

前言&#xff1a; 上vip课的时候每次讲到框架的执行&#xff0c;就会有好学的同学问用多线程怎么执行&#xff0c;然后我每次都会说在测开课程会详细讲解&#xff0c;这并不是套路&#xff0c;因为如果你不理解多线程&#xff0c;不清楚什么时候该用什么时候不该用&#xff0c;…...

惬意上手Python —— 装饰器和内置函数

1. Python装饰器 Python中的装饰器是一种特殊类型的函数&#xff0c;它允许用户在不修改原函数代码的情况下&#xff0c;增加或修改函数的行为。 具体来说,装饰器的工作原理基于Python的函数也是对象这一事实&#xff0c;可以被赋值给变量、作为参数传递给其他函数或者作为其他…...

python 调用dll

在Python中&#xff0c;可以使用ctypes库来调用DLL文件。ctypes库是一个标准库&#xff0c;用于在Python中加载共享库&#xff08;例如DLL文件&#xff09;并调用其中的函数。 以下是一个简单的示例&#xff0c;演示如何使用ctypes库调用DLL文件中的函数&#xff1a; import c…...

docker里Java服务执行ping命令模拟流式输出

文章目录 业务场景处理解决实现ping功能并实时返回输出实现长ping和中断请求docker容器找不到ping命令处理 业务场景 我们某市的客户&#xff0c;一直使用CS版本的信控平台&#xff0c;直接安装客户Windows server服务器上&#xff0c;主要对信号机设备进行在线管理、方案配时…...

代码随想录算法训练营第十三天| 239. 滑动窗口最大值 、347.前 K 个高频元素

239. 滑动窗口最大值 思路&#xff1a; 用遍历区间的元素时&#xff0c;维护一个单调队列&#xff0c;从大到小排列。 要找到最大值&#xff0c;实际单调队列保存区间内最大值及最大值右侧的第二大值&#xff08;用于当前最大值处于区间左端&#xff0c;在区间右移时更新临时最…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...