当前位置: 首页 > 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;在区间右移时更新临时最…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

嵌入式面试常问问题

以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...

免费批量Markdown转Word工具

免费批量Markdown转Word工具 一款简单易用的批量Markdown文档转换工具&#xff0c;支持将多个Markdown文件一键转换为Word文档。完全免费&#xff0c;无需安装&#xff0c;解压即用&#xff01; 官方网站 访问官方展示页面了解更多信息&#xff1a;http://mutou888.com/pro…...