【图论】最短路的传送问题

一.分层图问题(单源传送)

(1)题目

P4568 [JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

(2)思路

可知背景就是求最短路问题,但难点是可以使一条路距离缩短至0,那如何更好的利用这个机会呢?

此时我们可以用到分层图,如下:

即我们可以免费往下传一次,其实也就相当于两点距离为0了,这时终点应该9号节点。

于是建图如下:

			add(u+(j-1)*n,v+j*n,0);add(v+(j-1)*n,u+j*n,0);add(u+j*n,v+j*n,w);add(v+j*n,u+j*n,w);

第一个是从上到下,是使用传送的边

第二个是第一个的逆向

第三个是已经用过一次机会,已经在下面了,所以正常边

第四个是第三个的逆向

	for(int j=1;j<=k;j++){add(s+(j-1)*n,s+j*n,0);}

这个是特殊情况,起点即终点,一路传送,其实多此一举,但没办法,只怪我们把图分层了。不能在自环到达了。

(3)参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int s,e;
struct Edge{int u,v,w,next;
}edge[2500001];
int head[110005],cnt;
void add(int u,int v,int w){edge[++cnt]=(Edge){u,v,w,head[u]}; head[u]=cnt;
}
int dis[110005],vis[110005];
struct node{int u,w;bool operator < (const node &x) const{return x.w<w;}
};
void dijkstra(){priority_queue<node>q;memset(dis,0x3f,sizeof(dis));q.push((node){s,0});dis[s]=0;while(!q.empty()){node temp=q.top(); q.pop();int u=temp.u;if(vis[u]) continue;vis[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v,w=edge[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push((node){v,dis[v]});}}}
}
int main(){cin>>n>>m>>k>>s>>e;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);for(int j=1;j<=k;j++){add(u+(j-1)*n,v+j*n,0);add(v+(j-1)*n,u+j*n,0);add(u+j*n,v+j*n,w);add(v+j*n,u+j*n,w);}}for(int j=1;j<=k;j++){add(s+(j-1)*n,s+j*n,0);}dijkstra();cout<<dis[e+k*n];return 0;
}

二.多源传送

(1)题目

P6464 [传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

(2)思路

这题虽然是多源,但只有一个传送门,而且数据范围小,只有100,所以直接上floyd算法!

因为我们不知道传送门怎么建立,所以直接暴力枚举就行了。

我们两重遍历,找出门,在两重暴力folyd即可。

Q:folyd不是三重吗?

A:不是已经知道在哪搭桥了吗?

Q:其他不也可以搭桥吗?

A:前面的预处理三重floyd已经处理好了。

(3)参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[101][101];
int F[101][101];
inline void back()
{for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)F[i][j]=f[i][j];
}
int main()
{scanf("%d%d",&n,&m);memset(f,-1,sizeof(f));for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);if(f[u][v]==-1||f[u][v]>w)	f[u][v]=f[v][u]=w;//建边,防重边(不过数据里没有)}for(int k=1;k<=n;k++)	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(f[i][k]!=-1&&f[k][j]!=-1)if(f[i][j]==-1||f[i][j]>f[k][j]+f[i][k])f[i][j]=f[i][k]+f[k][j];//Floydint ans=2e9;//较大值for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)//暴力枚举{back();//先让F数组还原成f数组F[i][j]=F[j][i]=0;//在教学楼 i 和 j 之间建立传送门//i点搭桥 for(int x=1;x<=n;x++)	for(int y=1;y<=n;y++)	if(F[x][y]==-1||F[x][y]>F[x][i]+F[i][y])F[x][y]=F[x][i]+F[i][y];//Floyd//j点搭桥 for(int x=1;x<=n;x++)for(int y=1;y<=n;y++)	if(F[x][y]==-1||F[x][y]>F[x][j]+F[j][y])F[x][y]=F[x][j]+F[j][y];//Floydint res=0;for(int x=1;x<=n;x++)	for(int y=1;y<x;y++)res+=F[x][y];ans=min(res,ans);}printf("%d\n",ans);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/97569.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

抓包工具Fiddler下载与安装

一、Fiddler介绍 1.Fiddler简介 Fiddler 是一款免费、灵活、操作简单、功能强大的 HTTP 代理工具&#xff0c;是目前最常用的 HTTP 抓包工具之一。可以抓取所有的 HTTP/HTTPS 包、过滤会话、分析请求详细内容、伪造客户端请求、篡改服务器响应、重定向、网络限速、断点调试等…

【IMX6ULL驱动开发学习】06.DHT11温湿度传感器驱动程序编写与测试

一、DHT11简介 DHT11是一款可测量温度和湿度的传感器。比如市面上一些空气加湿器&#xff0c;会测量空气中湿度&#xff0c;再根据测量结果决定是否继续加湿。 DHT11数字温湿度传感器是一款含有已校准数字信号输出的温湿度复合传感器&#xff0c;具有超小体积、极低功耗的特点…

JQuery快速入门教程

1、JQuery快速入门 1.1、JQuery介绍 jQuery 是一个 JavaScript 库。所谓的库&#xff0c;就是一个 JS 文件&#xff0c;里面封装了很多预定义的函数&#xff0c;比如获取元素&#xff0c;执行隐藏、移动等&#xff0c;目的就 是在使用时直接调用&#xff0c;不需要再重复定义…

【Unity开发必备】100多个 Unity 学习网址 资源 收藏整理大全【持续更新】

Unity 相关网站整理大全 众所周知&#xff0c;工欲善其事必先利其器&#xff0c;有一个好的工具可以让我们事半功倍&#xff0c;有一个好用的网站更是如此&#xff01; 但是好用的网站真的太多了&#xff0c;收藏夹都满满的(但是几乎没打开用过&#x1f601;)。 所以本文是对…

开源ChatGPT系统源码 采用NUXT3+Laravel9后端开发 前后端分离版本

开源ChatGPT系统源码 采用NUXT3Laravel9后端开发 前后端分离版本 ChatGPT是一种基于AI的聊天机器人技术&#xff0c;它可以帮助用户与聊天机器人进行自然语言交流&#xff0c;以解决用户的问题或满足用户的需求。ChatGPT的核心技术是使用自然语言处理&#xff08;NLP&#xff…

Linux/Ubuntu 的日常升级和安全更新,如何操作?

我安装的是Ubuntu 20.04.6 LTS的Windows上Linux子系统版本&#xff0c;启动完成后显示&#xff1a; Welcome to Ubuntu 20.04.6 LTS (GNU/Linux 5.15.90.4-microsoft-standard-WSL2 x86_64) * Documentation: https://help.ubuntu.com * Management: https://landscape.c…

P6685 可持久化动态仙人掌的直径问题

思路1&#xff1a;二分快速幂 #include<bits/stdc.h> using namespace std; #define int long long int n,m; bool check(int a,int b){int ans1;while(b){if(a>n)return false;if(b&1)ans*a;if(ans>n)return false;aa*a;b>>1;}return ans<n; } voi…

AI重新定义音视频生产力“新范式”

// 编者按&#xff1a;AIGC无疑是当下的热门话题和场景。面对AI带来的技术变革和算力挑战&#xff0c;该如何应对&#xff1f;LiveVideoStackCon 2023上海站邀请到了网心科技副总裁武磊为我们分享网心在面对AI应用场景和业务需求下的实践经验。 文/武磊 编辑/LiveVideoStack …

元宇宙电商—NFG系统:区块链技术助力商品确权。

在国内&#xff0c;以“数字藏品”之名崛起以来&#xff0c;其与NFT的对比就从未停歇。从上链模式到数据主权&#xff0c;从炒作需求到实际应用&#xff0c;从售卖形式到价值属性&#xff0c;在各种抽丝剥茧般的比较中&#xff0c;围绕两者孰优孰劣的讨论不绝于耳。 NFT的每一…

从NLP到聊天机器人

一、说明 今天&#xff0c;当打电话给银行或其他公司时&#xff0c;听到电话另一端的机器人向你打招呼是很常见的&#xff1a;“你好&#xff0c;我是你的数字助理。请问你的问题。是的&#xff0c;机器人现在不仅可以说人类语言&#xff0c;还可以用人类语言与用户互动。这是由…

Shell编程之正则表达式

文本处理器&#xff1a;三剑客&#xff1a;grep查找sed awk shell正则表达式由一类特殊字符以及文本字符所编写的一种模式&#xff0c;处理文本当中的内容&#xff0c;其中的一些字符不表示字符的字面含义表示一种控制或者通配的功能 通配符&#xff1a;匹配文件名和目录名&a…

List和ObservableCollection和ListBinding在MVVM模式下的对比

List和ObservableCollection和ListBinding在MVVM模式下的对比 List 当对List进行增删操作后&#xff0c;并不会对View进行通知。 //Employee public class Employee : INotifyPropertyChanged {public event PropertyChangedEventHandler? PropertyChanged;public string N…

VSCode无法从Extensions下载工具时,把工具下载到本地并添加到VSCode编辑器

从VSCode 的 Extensions 下载 下载报错&#xff1a;Error while installing ...... extension. Please check the log for more details. 由于内网限制&#xff08;或者其他网络限制&#xff09;无法正常下载扩展工具到VSCode编辑器&#xff0c;可以把工具下载到本地再添加到V…

Python的六种参数?

很多人说&#xff0c;Python的参数类型有四种、五种&#xff0c;我个人认为归纳起来是六种参数&#xff0c;分别为&#xff1a;位置参数&#xff08;Positional Arguments&#xff09;、默认参数&#xff08;Default Arguments&#xff09;、关键字参数&#xff08;Keyword Arg…

Autosar存储入门系列02_NVM之CRC校验及显隐式同步机制

本文框架 0.前言1. NVM中CRC校验2. NVM的显隐式同步机制2.1 隐式同步2.2 显式同步 0.前言 本系列是Autosar存储入门系列&#xff0c;希望能从学习者的角度把存储相关的知识点梳理一遍&#xff0c;这个过程中如果大家觉得有讲得不对或者不够清晰的地方&#xff0c;还请一定指出…

如何做好服务性能测试

一、什么是性能测试 新功能上线或切换底层数据库或扩容调优&#xff0c;根据实际业务场景的需要&#xff0c;做必要的性能压测&#xff0c;收集性能数据&#xff0c;作为上线的基准报告。 性能测试一般分一下几个阶段&#xff1a; 1. 性能测试 并发量小&#xff08;jmeter 并…

windows服务器下java程序健康检测及假死崩溃后自动重启应用、开机自动启动

前两天由于项目需要&#xff0c;一个windows上的批处理任务&#xff08;kitchen.bat&#xff09;&#xff0c;需要接到mq的消息通知后执行&#xff0c;为了快速实现这里我们通过springboot写了一个jar程序&#xff0c;用于接收mq的消息&#xff0c;并调用bat文件。 本程序需要实…

Field injection is not recommended

文章目录 1. 引言2. 不推荐使用Autowired的原因3. Spring提供了三种主要的依赖注入方式3.1. 构造函数注入&#xff08;Constructor Injection&#xff09;3.2. Setter方法注入&#xff08;Setter Injection&#xff09;3.3. 字段注入&#xff08;Field Injection&#xff09; 4…

【Unity每日一记】SceneManager场景资源动态加载

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;uni…

【Redis基础篇】浅谈分布式系统(一)

一、浅谈分布式系统 1. 单机架构&#xff1a;只有一台服务器&#xff0c;这个服务器负责所有的工作。 如果遇到了服务器不够的场景怎么处理? 开源&#xff1a;增加更多的硬件资源节流&#xff1a;软件上的优化&#xff0c;优化代码等…一台服务器资源使用有限&#xff0c;就…