[最短路dijkstra],启动!!!
总时间复杂度为 O ( ( n + m ) log m )
P4779 【模板】单源最短路径(标准版)
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e5+5;
int n,m,s;
vector<PII> v[N];
int dis[N];
bool vis[N];
void dijkstra(int s)
{priority_queue<PII,vector<PII>,greater<PII> > q;//for(int i=1;i<=n;i++) dis[i] = 1e9;q.push({0,s});//dis[s] = 0;while(q.size()){auto t = q.top();//q.pop();int now = t.se;//if(vis[now]==1) continue;//vis[now] = 1;//for(auto tt:v[now]){int spot = tt.fi,w = tt.se;if(dis[spot]>dis[now]+w){dis[spot] = dis[now]+w;q.push({dis[spot],spot});//}}}
}
int main()
{IOS;cin>>n>>m>>s;while(m--){int a,b,w;cin>>a>>b>>w;v[a].pb({b,w});} dijkstra(s);for(int i=1;i<=n;i++) cout<<dis[i]<<' ';return 0;
}
P3905 道路重建
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+5;
int n,m,A,B;
int va[10005][10005];
vector<PII> v[N];
int dis[N];
bool vis[N];
void dijkstra(int s)
{priority_queue<PII,vector<PII>,greater<PII> > q;for(int i=1;i<=n;i++) dis[i] = 1e9;dis[s] = 0;q.push({0,s});while(q.size()){auto t = q.top();q.pop();int now = t.se;if(vis[now]==1) continue;vis[now] = 1;for(auto tt:v[now]){int spot = tt.fi,w = 0;if(va[now][spot]==1) w = tt.se;if(dis[spot]>dis[now]+w){dis[spot] = dis[now]+w;q.push({dis[spot],spot});} }}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,w;cin>>a>>b>>w;v[a].pb({b,w});v[b].pb({a,w});} int d;cin>>d;while(d--){int a,b;cin>>a>>b;va[a][b] = 1;va[b][a] = 1; }cin>>A>>B;dijkstra(A);cout<<dis[B];
}
P4554 小明的游戏
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair< int,pair<int,int> >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e4+5;
int n,m,s,stx,sty,edx,edy;
int dis[N][N];
bool vis[N][N];
char va[N][N];
int dx[4] ={0,0,1,-1};
int dy[4] ={1,-1,0,0};
void distra()
{priority_queue<PII,vector<PII>,greater<PII> > q;//for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dis[i][j] = 1e9;vis[i][j] = 0;}}q.push({0,{stx,sty}});//dis[stx][sty] = 0;while(q.size()){auto t = q.top();//q.pop();auto now = t.se;//int x = now.fi,y = now.se;if(vis[x][y]==1) continue;//vis[x][y] = 1;//for(int i=0;i<=3;i++){int xx = x+dx[i],yy = y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m){int w = 0;if(va[x][y]!=va[xx][yy]) w = 1;if(dis[xx][yy]>dis[x][y]+w){dis[xx][yy] = dis[x][y]+w;q.push({dis[xx][yy],{xx,yy}});//}}}}
}
int main()
{IOS;while(1) {cin>>n>>m;if(n==0&&m==0) break;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>va[i][j];}}cin>>stx>>sty>>edx>>edy;stx += 1;sty += 1;edx += 1;edy += 1;distra();cout<<dis[edx][edy]<<"\n";}
}
相关文章:
[最短路dijkstra],启动!!!
总时间复杂度为 O ( ( n m ) log m ) P4779 【模板】单源最短路径(标准版) #include<bits/stdc.h> #define ll long long #define fi first #define se second #define pb push_back #define PII pair<int,int > #define I…...

Java企业微信服务商代开发获取AccessToken示例
这里主要针对的是企业微信服务商代开发模式 文档地址 可以看到里面大致有三种token,一个是服务商的token,一个是企业授权token,还有一个是应用的token 这里面主要有下面几个参数 首先是服务商的 corpid 和 provider_secret ,这个可…...

How does age change how you learn?(2)年龄如何影响学习能力?(二)
Do different people experience decline differently? 不同人经历的认知衰退会有不同吗? Do all people experience cognitive decline uniformly?Or do some people’s minds slip while others stay sharp much longer? 所有人经历的认知衰退都是一样的吗?还是有些人…...
可验证随机函数 vrf 概述
一、什么是VRF 背景: 在传统的区块链中,常用的随机算法是基于伪随机数生成器(Pseudorandom Number Generator,PRNG)的。PRNG是一种确定性算法,它根据一个初始种子生成一个看似随机的序列。在区块链中,通常使用的是伪随机数序列来选择区块的创建者、确定验证节点的轮换…...

鸿蒙双向绑定组件:TextArea、TextInput、Search、Checkbox,文本输入组件,图案解锁组件PatternLock
对象暂不支持双向绑定, 效果: 代码: Entry Component struct MvvmCase {StateisSelect: boolean falseStatesearchText: String ""StateinputText: string ""StateareaText: string ""build() {Grid() {G…...
JS 算法 - 计数器
theme: smartblue 题目描述 给定一个整型参数 n,请你编写并返回一个 counter 函数。这个 counter 函数最初返回 n,每次调用它时会返回前一个值加 1 的值 ( n , n 1 , n 2 ,等等)。 示例 1: 输入: n 10 ["cal…...

JavaScript基础——JavaScript运算符
赋值运算符 算术运算符 一元运算符 三元/三目运算符 比较运算符 逻辑运算符 运算符优先级 在JavaScript中,常见的运算符可以包括赋值运算符、一元运算符、算术运算符(二元运算符)、三元/三目运算符、比较运算符、逻辑运算符等࿰…...
E23.【C语言】练习:不创建第三个变量实现两个整数的交换
目录 题目条件 思路1( -) 思路2 (^)(XOR) 往期推荐 1.题目条件 禁止使用以上代码 2.思路1: -运算 aab; ba-b; aa-b; 但这样有潜在的问题 :a,b存储的数字过大,ab可能超过范围 因此改用思路2…...
如何搭建一个web系统?
需求 搭建一个web系统。 框架 设计:墨刀 前端:Vue.js 后端:Java 算法:Python 数据库:时序数据库,介绍 部署:Jekins https://www.jenkins.io/ 文档管理:Teambition 项目管理:禅道 代码管理:Gitlab 开发流程 设计文档和原型文档,功能接口设计࿰…...

三十种未授权访问漏洞复现 合集( 二 )
未授权访问漏洞介绍 未授权访问可以理解为需要安全配置或权限认证的地址、授权页面存在缺陷,导致其他用户可以直接访问,从而引发重要权限可被操作、数据库、网站目录等敏感信息泄露。---->目录遍历 目前主要存在未授权访问漏洞的有:NFS服务&a…...
C语言学习笔记[29]:函数①
函数 在C语言中,函数是一段可以完成特定功能的代码,它们可以被重复调用。 函数的分类: 库函数自定义函数 库函数 在C语言中,库函数是由系统提供的,用于完成特定功能的函数,这些函数被集合在一起&#…...

使用Springboot + netty 打造聊天服务之Nacos集群问题记录
目录 1、前言1.1、方法一1.2、方法二 2、方案二实战2.1、在netty服务里加上ws连接、中断事件2.2、在netty服务里加上消息服务 4、总结 使用Springboot netty 打造聊天服务系列文章 第一章 初始搭建工程 第二章 Nacos集群问题记录 1、前言 在使用Springboot Nacos Netty(Web…...

全网唯一!R语言顶刊配色包TheBestColors
与Matlab相比,R语言在绘图方面有着天然的优势。 比如在配色方面,R语言有各式各样现成的包,按理说配色这种事应该很方便才对。 但实际体验下来,发现似乎不是那么回事。 首先,你很难记住每个包的调用方法以及每种配色…...

链表题型思路错误总结
常见题目 206. 反转链表 关键点:定义前置指针。 在给cur.next复制前,需要定义好next节点防止断链。 public ListNode reverseList(ListNode head) {if (head null || head.next null) {return head;}ListNode pre null;ListNode cur head;while(cur…...

算法学习day28
一、寻找右区间(二分法) 题意:题目很容易理解 但是转换为二分法有点晦涩 给你一个区间数组 intervals ,其中 intervals[i] [starti, endi] ,且每个 starti 都 不同 。区间 i 的 右侧区间 可以记作区间 j ,并满足 startj > e…...
C语言基础题:迷宫寻路(C语言版)
1.题目描述 机器猫被困在一个矩形迷宫里。 迷宫可以视为一个n x m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。 机器猫初始时位于(1,1)的位置,问能否走到(n,m)位置。 2.输入格式 第一行࿰…...

力扣-1两数之和2两数相加-2024/8/3
1、两数之和 解法一 暴力法(2个for循环) class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:for ii in range(len(nums)):for jj in range(ii1, len(nums)):if nums[ii]nums[jj] target:return [ii,jj]解法二 哈希表法…...
简站WordPress主题 专业的WordPress建站服务商
简站WordPress主题是一款备受推崇的WordPress主题,以其简洁、实用、无插件和更安全的特性脱颖而出。以下是关于简站WordPress主题的一些详细分析: 简站WordPress主题采用了扁平化设计风格,界面简洁明了,这使得网站看起来更加专业…...

Final Shell for Mac 虚拟机连接工具【简单易操作,轻松上手】【开发所需连接工具】
Mac分享吧 文章目录 效果一、下载软件二、安装软件三、运行测试安装完成!!! 效果 一、下载软件 下载软件 链接:http://www.macfxb.cn 二、安装软件 三、运行测试 安装完成!!!...
Oracle JDK:版本、支持与许可
文章目录 版本支持许可BCLOTNNFTCFAQ其他OpenJDK和其他的JDK实现JDK、JRE、JVMJava SE、Java EE、Java ME版本 Oracle JDK的最新版本和历史版本的官方下载地址(可查询版本发行说明等信息):https://www.oracle.com/cn/java/technologies/downloads/ 常规版本(非LTS):每隔…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...

深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...