[最短路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):每隔…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...