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

[最短路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 …...

大模型是否潜在地进行多跳推理?

人工智能咨询培训老师叶梓 转载标明出处 以往的研究表明&#xff0c;基于Transformer的LLMs能够在参数中存储和检索事实信息&#xff0c;以完成简单提示&#xff0c;例如“Stevie Wonder的母亲是谁”。此外&#xff0c;当必要信息明确给出时&#xff0c;LLMs表现出了显著的上下…...

人为什么不能长期待在家里?三个原因告诉你答案

在现代社会的快节奏生活中,人们时常渴望能够拥有一段长时间待在家里的闲暇时光,幻想这会是一段惬意、舒适且自由的经历。然而,实际情况往往并非如此。许多人在经历了数日甚至更长时间的居家生活后,会逐渐感受到诸多负面情绪和不良影响。以下将详细阐述人为什么不能长期待在…...

MATLAB画散点密度图(附代码和测试数据的压缩包)

1. 有关 Matlab 获取代码关注WZZHHH回复关键词&#xff0c;或者咸鱼关注&#xff1a;WZZHHH123 怀俄明探空站数据解算PWV和Tm&#xff1a;怀俄明探空站数据解算PWV和Tm 怀俄明多线程下载探空站数据&#xff08;包括检查和下载遗漏数据的代码&#xff09;&#xff1a;怀俄明多线…...

SSH配置命令

前置环境&#xff1a;端口配置IP地址&#xff0c;client和server之间可ping通&#xff0c;此处省略 server端: 开启stelnet [Huawei]stelnet server enable Info: Succeeded in starting the Stelnet server. aaa模式相关配置 #进入aaa模式 [Huawei]aaa # 添加用户admin和…...

谷粒商城实战记录-虚拟机开启密码认证登录

文章目录 一&#xff0c;虚拟机无法用用户名密码登录二&#xff0c;解决方案1&#xff0c;修改配置2&#xff0c;重启sshd服务3&#xff0c;测试SSH登录注意事项结论 参考文献 一&#xff0c;虚拟机无法用用户名密码登录 当使用Vagrant创建和管理虚拟机时&#xff0c;通常会通…...

C语言程序设计-[1] 基础语法

1、字符集 字符集&#xff1a;是ASCII字符集的一个子集。 注&#xff1a;基本上就是电脑键盘可以输入的一些字符。 2、标识符 标识符&#xff1a;用来命名程序中的一些实体&#xff0c;如&#xff1a;变量、常量、函数、数组名、类型名、文件名等。由一个或多个字符组成。 —…...

JavaSE第11篇:设计模式

一、创建型模式 1、工厂方法模式 2、抽象工厂模式 3、单例模式singleton /*** 单例* 饿汉式(线程安全的):在加载类的时候就会创建类的单例&#xff0c;并保存在类中。* 1.定义类变量实例并直接实例化&#xff0c;在类加载的时候就完成了实例化并保存在类中;* 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 值&#xff1f;方式 1 | xprop 命令方式 2 | 直接查看 问题描述 这个启动器无论是在菜单还是桌面都是正常的&#xff0c;只有在dock中没有图标&#xff0c;且不像其他APP…...

【Android】数据持久化——数据存储

持久化技术简介 在你打开完成了一份PPT之后关闭程序&#xff0c;再次打开肯定是希望之前的内容还存在在电脑上&#xff0c;一打开PPT&#xff0c;之前的内容就自动出现了。数据持久化就是将那些内存中的瞬时数据保存到存储设备中&#xff0c;保证即使在手机或电脑关机的情况下…...

如何通过谷歌外链快速增加网站流量?

利用谷歌外链提升流量的方法非常直接&#xff0c;但实际上&#xff0c;外链影响的是关键词排名&#xff0c;关键词排名提升了&#xff0c;自然就会有流量&#xff0c;所以谷歌外链不是直接能提升网站流量&#xff0c;而是间接的&#xff0c;下面&#xff0c;我会详细介绍几种有…...

vLLMcuda安装笔记

1. 引言 最近在部署Qwen模型时&#xff0c;文档上有提到强烈建议用vLLM来部署模型&#xff0c;按照公开的性能测试数据&#xff0c;用vLLM部署Qwen模型的文本推理速度要比transformers部署快3~4倍。带着这个好奇就开始安装尝试&#xff0c;但试下来这个安装过程并没有那么顺利…...

C++入门基本语法(2)

一、引用 1、基本概念与定义 引用不是新定义一个变量&#xff0c;而是给已存在的变量起一个别名&#xff0c;编译器不会为引用变量开辟内存空间&#xff0c;它和它所引用的变量公用同一块内存空间&#xff1b; 引用的写法&#xff1a;变量类型& 引用别名 变量&#xff…...

Internet Download Manager(IDM)2024中文版本有哪些新功能?6.42版本功能介绍

1. Internet Download Manager&#xff08;IDM&#xff09;是一款功能强大的下载管理器&#xff0c;支持所有流行的浏览器&#xff0c;并可提升下载速度高达5倍。 2. IDM具有智能下载逻辑加速器&#xff0c;可以设置文件下载优先级、分块下载等&#xff0c;提高下载效率。 IDM…...

深入理解 C 语言中的联合体

目录 引言 一、 联合体的定义与基本用法 1.联合体的定义 2.基本用法 二、 联合体与结构体的区别 1.结构体 2.联合体 3.对比 三、联合体的优势 1. 节省内存 2. 提高效率 3. 代码简洁性 四、联合体的存储细节 1.内存对齐 2.大小计算 五、联合体的高级用法 1.匿…...

OpenCV||超详细的几何变换

2D图像几何变换的33矩阵&#xff1a; 图像常见的几何变换&#xff1a; 图像来源&#xff1a;《OpenCV 4.5计算机视觉开发实战&#xff1a;基于Python》作者&#xff1a;朱文伟 李建英&#xff1b; 1. 平移&#xff08;Translation&#xff09; 在OpenCV中&#xff0c;平移不是…...

网络程序设计基础概述

文章目录 前言一、网络程序设计基础二、网络协议 1.IP协议2.TCP与UDP协议三、端口与套接字总结 前言 网络程序设计编写的是与其他计算机进行通信的程序代码。Java将网络程序所需要的东西封装成了不同的类。开发者只需要创建这些类的对象&#xff0c;调用相应的方法&#xff0c;…...

MySQL:数据库用户

数据库用户 在关系型数据库管理系统中&#xff0c;数据库用户&#xff08;USER&#xff09;是指具有特定权限和访问权限的登录账户。每个用户都有自己的用户名和密码&#xff0c;以便系统可以通过认证来识别他们的身份。数据库用户可以登录数据库&#xff0c;在其中执行各种类…...

用TensorFlow训练自己的第一个模型

现在学AI的一个优势就是&#xff1a;前人栽树后人乘凉&#xff0c;很多资料都已完善&#xff0c;而且有很多很棒的开源作品可以学习&#xff0c;感谢大佬们 项目 项目源码地址 视频教程地址 我在大佬的基础上基于此模型还加上了根据特征值缓存进行快速识别的方法&#xff0c;…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...