[最短路SPFA]--启动!!!!!
基础模板
#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+10;
int n,m,s;
//int cnt[N];
bool vis[N];
int dis[N];
vector<PII> v[N];
//bool suc = 0;
void spfa(int s)
{queue<int> q;for(int i=1;i<=n;i++){//v[i].clear();//1.测试多组数据,并且每组数据重新建边时加上dis[i] = 1e9;//vis[i] = 0;//cnt[i] = 0;//在1.的情况下,还要查询负环时加上}vis[s] = 1;dis[s] = 0;q.push(s);while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w = t.se;if(dis[spot]>dis[now]+w){//cnt[spot] = cnt[now]+1;//查询负环时加上//if(cnt[spot]>=n)//{// suc= 1;// return;//}dis[spot] = dis[now]+w;if(vis[spot]==0){vis[spot]=1;q.push(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});//双向边时候加上}cin>>s;//s为初始起点spfa(s);
}
P3371 【模板】单源最短路径(弱化版)
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m,s;
vector< pair<int,int> > v[N];//v[s][i].fi是初始点s能走到的第i个的点,v[s][i].se初始点s能走到
int dis[N];//是从初始点s到第i个点的最短路程
bool vis[N];//标记该点是否被走过了
void spfa()
{for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0; }queue<int> q;q.push(s);dis[s] = 0;vis[s] = 1;while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w =t.se;if(dis[spot]>dis[now]+w){dis[spot] = dis[now]+w; if(vis[spot]==0){vis[spot] = 1;q.push(spot);} }}}
}
int main()
{IOS;cin>>n>>m>>s;while(m--){int a,b,c;cin>>a>>b>>c;v[a].pb({b,c});//v[b].pb({a,c});加上为无向边,不加为单向边 }spfa();for(int i=1;i<=n;i++){if(dis[i]==1e9) cout<<(1ll<<31)-1<<' ';else cout<<dis[i]<<" ";}}
P3385 【模板】负环
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m;
bool vis[N];
int dis[N];
int cnt[N];//1.加个数组
vector<PII> v[N];
//2.cnt[i]表示走到第i个点时用了几条边,一般最大为n-1条,如果存在负环, 则会>=n
bool spfa()//3.改为bool
{queue<int> q;for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;cnt[i] = 0;//查负环时加上}//初始化vis[1] = 1;dis[1] = 0; q.push(1);while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w = t.se;if(dis[spot]>dis[now]+w){cnt[spot] = cnt[now]+1;//4.记录已用环数 if(cnt[spot]>=n) return true; //5.一定要返回,不然会一直重复去加负权 //如 5 -> 6边权为2, 6 -> 5边权为-3,便会一直+2-3下去,越加越爽,爽到负无穷 dis[spot] = dis[now]+w;if(vis[spot]==0){q.push(spot);vis[spot]=1;}}}}return false;//6.没有负环
}
int main()
{IOS;int k;cin>>k;while(k--){cin>>n>>m;for(int i=1;i<=max(n,m);i++){v[i].clear();//多组数据时加上dis[i] = 1e9;vis[i] = 0;cnt[i] = 0;}while(m--){int a,b,c;cin>>a>>b>>c;if(c>=0) v[a].pb({b,c}),v[b].pb({a,c});else v[a].pb({b,c});}if(spfa()) cout<<"YES"<<"\n";else cout<<"NO"<<"\n";} }
那如果存在非连通的点呢?
//从原点n+1开始搜bool spfa()//3.改为bool
{queue<int> q;for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;cnt[i] = 0;//查负环时加上}//初始化vis[n+1] = 1;//从原点n+1开始搜,详情见7.--- dis[n+1] = 0; q.push(n+1);
}
int main()
{for(int i=1;i<=n;i++)//7.注意!!如果各点可能不是全部连通,如果从1开始会搜不到另一部分的负权{ //所以建立一个点把所有点连接起来,我们就设它为n+1v[n+1].pb({i,0});//从n+1开始到所有的点,边权为零不会影响结果 }
}
P3905 道路重建
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e6+10;
int n,m,d,A,B;
int dis[N];
bool vis[N];
vector<PII> v[N];
map<pair<int,int>,int> mp;
void spfa()
{for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;}//初始化queue<int> q;q.push(A);dis[A] = 0;vis[A] = 1;while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w = 0; if(mp[{now,spot}]==1) w = t.se;//这条路如果被炸过了,那么就把他的长度算上,去修它 if(dis[spot]>dis[now]+w){dis[spot] = dis[now]+w; if(vis[spot]==0){vis[spot] = 1;q.push(spot);} }}}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,c;cin>>a>>b>>c;v[a].pb({b,c});v[b].pb({a,c});}cin>>d;while(d--){int a,b;cin>>a>>b;mp[{a,b}] = 1;//标记a -> bb不能走 mp[{b,a}] = 1;//b -> a不能走 }cin>>A>>B;spfa();cout<<dis[B];
}
P1629 邮递员送信
#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+10;
int n,m;
vector<PII> v1[N];
vector<PII> v2[N];
bool vis1[N];
int dis1[N];
bool vis2[N];
int dis2[N];
int sum=0;
void spfa1(int s)
{queue<int> q;vis1[s] = 1;for(int i=1;i<=n;i++){dis1[i] = 1e9;vis1[i] = 0;}//初始化dis1[s] = 0;q.push(s);while(q.size()){int now = q.front();q.pop();vis1[now] = 0;for(auto t:v1[now]){int spot = t.fi,w = t.se;if(dis1[spot]>dis1[now]+w){dis1[spot] = dis1[now]+w;if(vis1[spot]==0){vis1[spot] = 1;q.push(spot);}}}}
}
void spfa2(int s)
{queue<int> q;vis2[s] = 1;for(int i=1;i<=n;i++){dis2[i] = 1e9;vis2[i] = 0;}//初始化dis2[s] = 0;q.push(s);while(q.size()){int now = q.front();q.pop();vis2[now] = 0;for(auto t:v2[now]){int spot = t.fi,w = t.se;if(dis2[spot]>dis2[now]+w){dis2[spot] = dis2[now]+w;if(vis2[spot]==0){vis2[spot] = 1;q.push(spot);}}}}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,l;cin>>a>>b>>l;v1[a].pb({b,l});v2[b].pb({a,l});//从所有的点走到1的路径,反向建边,让1替他们走一遍,避免了每个点都调用一次spfa导致超时} spfa1(1);spfa2(1);for(int i=1;i<=n;i++){sum+=dis1[i];sum+=dis2[i];}cout<<sum;
}
P2136 拉近距离
#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+10;
int n,m,T;
int cnt[N];
bool vis[N];
int dis[N];
vector<PII> v[N];
bool suc = 0;
void spfa(int s)
{queue<int> q;for(int i=1;i<=n;i++){dis[i] = 1e9;vis[i] = 0;cnt[i] = 0;}vis[s] = 1;dis[s] = 0;q.push(s);while(q.size()){int now = q.front();q.pop();vis[now] = 0;for(auto t:v[now]){int spot = t.fi,w = t.se;if(dis[spot]>dis[now]-w){cnt[spot] = cnt[now]+1;if(cnt[spot]>=n){suc= 1;return;}dis[spot] = dis[now]-w;if(vis[spot]==0){vis[spot]=1;q.push(spot);}}}}
}
int main()
{IOS;cin>>n>>m;while(m--){int a,b,w;cin>>a>>b>>w;v[a].pb({b,w});}int minn=1e9;spfa(1);minn = min(minn,dis[n]);spfa(n);//小红也会干事情来拉近距离 ,靠!!!! minn = min(minn,dis[1]);if(suc) cout<<"Forever love";else cout<<minn;
}相关文章:
[最短路SPFA]--启动!!!!!
基础模板 #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 1e610; int …...
大模型是否潜在地进行多跳推理?
人工智能咨询培训老师叶梓 转载标明出处 以往的研究表明,基于Transformer的LLMs能够在参数中存储和检索事实信息,以完成简单提示,例如“Stevie Wonder的母亲是谁”。此外,当必要信息明确给出时,LLMs表现出了显著的上下…...
人为什么不能长期待在家里?三个原因告诉你答案
在现代社会的快节奏生活中,人们时常渴望能够拥有一段长时间待在家里的闲暇时光,幻想这会是一段惬意、舒适且自由的经历。然而,实际情况往往并非如此。许多人在经历了数日甚至更长时间的居家生活后,会逐渐感受到诸多负面情绪和不良影响。以下将详细阐述人为什么不能长期待在…...
MATLAB画散点密度图(附代码和测试数据的压缩包)
1. 有关 Matlab 获取代码关注WZZHHH回复关键词,或者咸鱼关注:WZZHHH123 怀俄明探空站数据解算PWV和Tm:怀俄明探空站数据解算PWV和Tm 怀俄明多线程下载探空站数据(包括检查和下载遗漏数据的代码):怀俄明多线…...
SSH配置命令
前置环境:端口配置IP地址,client和server之间可ping通,此处省略 server端: 开启stelnet [Huawei]stelnet server enable Info: Succeeded in starting the Stelnet server. aaa模式相关配置 #进入aaa模式 [Huawei]aaa # 添加用户admin和…...
谷粒商城实战记录-虚拟机开启密码认证登录
文章目录 一,虚拟机无法用用户名密码登录二,解决方案1,修改配置2,重启sshd服务3,测试SSH登录注意事项结论 参考文献 一,虚拟机无法用用户名密码登录 当使用Vagrant创建和管理虚拟机时,通常会通…...
C语言程序设计-[1] 基础语法
1、字符集 字符集:是ASCII字符集的一个子集。 注:基本上就是电脑键盘可以输入的一些字符。 2、标识符 标识符:用来命名程序中的一些实体,如:变量、常量、函数、数组名、类型名、文件名等。由一个或多个字符组成。 —…...
JavaSE第11篇:设计模式
一、创建型模式 1、工厂方法模式 2、抽象工厂模式 3、单例模式singleton /*** 单例* 饿汉式(线程安全的):在加载类的时候就会创建类的单例,并保存在类中。* 1.定义类变量实例并直接实例化,在类加载的时候就完成了实例化并保存在类中;* 2.定义无参构造…...
【Unity Shader】切线空间下计算凹凸映射
// Upgrade NOTE: replaced mul(UNITY_MATRIX_MVP,*) with UnityObjectToClipPos(*)Shader "Unlit/NormalTangent" {Properties{_Color("Color Tint", Color) (1, 1, 1, 1)_MainTex("Main Tex", 2D) "While"{}//法线纹理_BumpMap(&q…...
解决Ubuntu/Kali手动创建的启动器在dock上没有图标,且不能“添加到dock中“的问题
文章目录 问题描述问题解决解决方案 1 | 添加StartupWMClass字段解决方案 2 | 重命名文件名 如何获取 WM 值?方式 1 | xprop 命令方式 2 | 直接查看 问题描述 这个启动器无论是在菜单还是桌面都是正常的,只有在dock中没有图标,且不像其他APP…...
【Android】数据持久化——数据存储
持久化技术简介 在你打开完成了一份PPT之后关闭程序,再次打开肯定是希望之前的内容还存在在电脑上,一打开PPT,之前的内容就自动出现了。数据持久化就是将那些内存中的瞬时数据保存到存储设备中,保证即使在手机或电脑关机的情况下…...
如何通过谷歌外链快速增加网站流量?
利用谷歌外链提升流量的方法非常直接,但实际上,外链影响的是关键词排名,关键词排名提升了,自然就会有流量,所以谷歌外链不是直接能提升网站流量,而是间接的,下面,我会详细介绍几种有…...
vLLMcuda安装笔记
1. 引言 最近在部署Qwen模型时,文档上有提到强烈建议用vLLM来部署模型,按照公开的性能测试数据,用vLLM部署Qwen模型的文本推理速度要比transformers部署快3~4倍。带着这个好奇就开始安装尝试,但试下来这个安装过程并没有那么顺利…...
C++入门基本语法(2)
一、引用 1、基本概念与定义 引用不是新定义一个变量,而是给已存在的变量起一个别名,编译器不会为引用变量开辟内存空间,它和它所引用的变量公用同一块内存空间; 引用的写法:变量类型& 引用别名 变量ÿ…...
Internet Download Manager(IDM)2024中文版本有哪些新功能?6.42版本功能介绍
1. Internet Download Manager(IDM)是一款功能强大的下载管理器,支持所有流行的浏览器,并可提升下载速度高达5倍。 2. IDM具有智能下载逻辑加速器,可以设置文件下载优先级、分块下载等,提高下载效率。 IDM…...
深入理解 C 语言中的联合体
目录 引言 一、 联合体的定义与基本用法 1.联合体的定义 2.基本用法 二、 联合体与结构体的区别 1.结构体 2.联合体 3.对比 三、联合体的优势 1. 节省内存 2. 提高效率 3. 代码简洁性 四、联合体的存储细节 1.内存对齐 2.大小计算 五、联合体的高级用法 1.匿…...
OpenCV||超详细的几何变换
2D图像几何变换的33矩阵: 图像常见的几何变换: 图像来源:《OpenCV 4.5计算机视觉开发实战:基于Python》作者:朱文伟 李建英; 1. 平移(Translation) 在OpenCV中,平移不是…...
网络程序设计基础概述
文章目录 前言一、网络程序设计基础二、网络协议 1.IP协议2.TCP与UDP协议三、端口与套接字总结 前言 网络程序设计编写的是与其他计算机进行通信的程序代码。Java将网络程序所需要的东西封装成了不同的类。开发者只需要创建这些类的对象,调用相应的方法,…...
MySQL:数据库用户
数据库用户 在关系型数据库管理系统中,数据库用户(USER)是指具有特定权限和访问权限的登录账户。每个用户都有自己的用户名和密码,以便系统可以通过认证来识别他们的身份。数据库用户可以登录数据库,在其中执行各种类…...
用TensorFlow训练自己的第一个模型
现在学AI的一个优势就是:前人栽树后人乘凉,很多资料都已完善,而且有很多很棒的开源作品可以学习,感谢大佬们 项目 项目源码地址 视频教程地址 我在大佬的基础上基于此模型还加上了根据特征值缓存进行快速识别的方法,…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
java高级——高阶函数、如何定义一个函数式接口类似stream流的filter
java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用(Math::max) 2 函数接口…...
OPENCV图形计算面积、弧长API讲解(1)
一.OPENCV图形面积、弧长计算的API介绍 之前我们已经把图形轮廓的检测、画框等功能讲解了一遍。那今天我们主要结合轮廓检测的API去计算图形的面积,这些面积可以是矩形、圆形等等。图形面积计算和弧长计算常用于车辆识别、桥梁识别等重要功能,常用的API…...
