Flody算法求解多源最短路问题

Flody算法求解多源最短路问题

在这里插入图片描述
在这里插入图片描述

蓝桥公园

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=409;
int n,m,q,d[N][N];
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m>>q;
  memset(d,0x3f,sizeof(d));//初始化d极大值
  for(int i=1;i<=n;i++)d[i][i]=0;//自己到自己距离为0
  while(m--){
    int u,v,w;cin>>u>>v>>w;
    d[u][v]=min(d[u][v],w);//双向图,可能有重边,取小
    d[v][u]=min(d[v][u],w);
  }
  for(int k=1;k<=n;k++)//Flody
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  while(q--){//q次询问
    int st,ed;cin>>st>>ed;
    if(d[st][ed]>=0x3f3f3f3f3f3f3f3f)cout<<"-1"<<'\n';//2e18也可
    else cout<<d[st][ed]<<'\n';
  }
}

小蓝组网

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=505;
int n,m,d[N][N];
bool ok=1;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m;
  memset(d,0x3f,sizeof(d));
  for(int i=1;i<=n;i++)d[i][i]=0;
  while(m--){
    int a,b;cin>>a>>b;
    d[a][b]=min(d[a][b],1LL);
    d[b][a]=min(d[b][a],1LL);
  }
  for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  int ans=0;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
      if(d[i][j]>=0x3f3f3f3f3f3f3f3f){
        ok=0;
        continue;
        }
      ans=max(ans,d[i][j]);
    }
  if(!ok)cout<<"NO"<<'\n';
  else cout<<"YES"<<'\n';
  cout<<ans;
}

最短路问题

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int n,q,g[N][N];
bool is_prime(int x){
    if(x<2)return 0;
    for (int i = 2; i*i <= x ; i ++ )
        if (x % i == 0)
            return 0;
    return 1;
}
void floyd(){
    for (int k = 1; k <= n; ++ k )
        for (int i = 1; i <= n; ++ i )
            for (int j = 1; j <= n; ++ j )
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main(){
    cin >> n >> q; 
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; ++ i )
        for (int j = i + 1; j <= n; ++ j )
            if (is_prime(i) + is_prime(j) == 1)
                g[i][j] = i*j/__gcd(i,j);
    
    floyd();
    
    while (q -- ){
        int a, b;cin >> a >> b;
        if (g[a][b] == 0x3f3f3f3f3f3f)cout<<"-1"<<'\n';
        else
            cout << g[a][b] <<'\n';
    }
}

会面

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
const int N = 209;
int n,m,g[N][N];
int s1,e1,s2,e2;
void floyd(){
    for (int k = 1; k <= n; ++ k )
        for (int i = 1; i <= n; ++ i )
            for (int j = 1; j <= n; ++ j )
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; ++ i )g[i][i] = 0;
    while (m -- ){
        int a, b, c;cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
        g[b][a]=min(g[b][a],c);
    }
    cin >> s1 >> e1 >> s2 >> e2;
    
    floyd();
    
    int res=0x3f3f3f3f3f;
    for (int k = 1; k <= n; ++ k )
        res=min(res,max(g[s1][k],g[s2][k])+max(g[k][e1],g[k][e2]));
    cout<<(res >= 0x3f3f3f3f3f? -1: res) << '\n';
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

mac 配置前端开发环境brew,git,nvm,nrm

我的电脑是mac 3 pro 一、配置Homebrew 打开终端&#xff0c;执行指令 /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"查看版本 brew -v 安装nvm brew install nvm 再执行 brew reinstall nvm 我这边安装好了…

云服务器上Docker启动的MySQL会自动删除数据库的问题

一、问题说明 除了常见的情况&#xff0c;例如没有实现数据挂载&#xff0c;导致数据丢失外&#xff0c;还需要考虑数据库是否被攻击&#xff0c;下图 REVOVER_YOUR_DATA 就代表被勒索了&#xff0c;这种情况通常是数据库端口使用了默认端口&#xff08;3306&#xff09;且密码…

Coding and Paper Letter(八十九)

CPL之第八十九期。 1 Coding: 1.openai通用代理转换是一个用于将其他厂商服务转为openai 标准接口相应的工具. 通过该工具, 可以将其他厂商的服务转为openai 标准接口. 讯飞星火,通义千问,gemini,openai,copilot,double&#xff0c;kimi&#xff0c;智谱清言 使用spring2webf…

Qt——示波器/图表 QCustomPlot

一、介绍 QCustomPlot是一个用于绘图和数据可视化的Qt C小部件。它没有进一步的依赖关系&#xff0c;提供友好的文档帮助。这个绘图库专注于制作好看的&#xff0c;出版质量的2D绘图&#xff0c;图形和图表&#xff0c;以及为实时可视化应用程序提供高性能。QCustomPlot可以导出…

机器学习和深度学习 -- 李宏毅(笔记与个人理解1-6)

机器学习和深度学习教程 – 李宏毅&#xff08;笔记与个人理解&#xff09; day1 课程内容 什么是机器学习 找函数关键技术&#xff08;深度学习&#xff09; 函数 – 类神经网络来表示 &#xff1b;输入输出可以是 向量或者矩阵等如何找到函数&#xff1a; supervised Lear…

【QingHub】EMQX单节点一键部署

EMQX 简介 EMQX是全球最具扩展性的开源MQTT 代理&#xff0c;具有高性能&#xff0c;可在 1 个集群中连接 1 亿多个 IoT 设备&#xff0c;同时保持每秒 100 万条消息的吞吐量和亚毫秒级的延迟。 EMQX 支持MQTT、HTTP、QUIC、WebSocket等多种开放标准协议。它 100% 符合MQTT 5.…

【Linux】tcpdump P3 - 过滤和组织返回信息

文章目录 基于TCP标志的过滤器格式化 -X/-A额外的详细选项按协议(udp/tcp)过滤低详细输出 -q时间戳选项 本文继续展示帮助你过滤和组织tcpdump返回信息的功能。 基于TCP标志的过滤器 可以根据各种TCP标志来过滤TCP流量。这里是一个基于tcp-ack标志进行过滤的例子。 # tcpdump…

大厂MVP技术JAVA架构师培养

课程介绍 这是一个很强悍的架构师涨薪计划课程&#xff0c;课程由专家级MVP讲师进行教学&#xff0c;分为是一个章节进行分解式面试及讲解&#xff0c;不仅仅是面试&#xff0c;更像是一个专业的架构师研讨会课程。课程内容从数据结构与算法、Spring Framwork、JVM原理、 JUC并…

每日Bug汇总--Day03

Bug汇总—Day03 一、项目运行报错 二、项目运行Bug 1、问题描述&#xff1a;Vue前端项目运行后台管理平台订单管理页面下的三个子页面出现点击不同的路由还是会出现相同的页面&#xff0c;导致页面和数据不匹配 解决办法&#xff1a; 在监听器中添加状态来根据路由地址变化…

C++ | Leetcode C++题解之第20题有效的括号

题目&#xff1a; 题解&#xff1a; class Solution { public:bool isValid(string s) {int n s.size();if (n % 2 1) {return false;}unordered_map<char, char> pairs {{), (},{], [},{}, {}};stack<char> stk;for (char ch: s) {if (pairs.count(ch)) {if (…

【mT5多语言翻译】之六——推理:多语言翻译与第三方接口设计

请参考本系列目录&#xff1a;【mT5多语言翻译】之一——实战项目总览 [1] 模型翻译推理 在分别使用全量参数微调和PEFT微调训练完模型之后&#xff0c;我们来测试模型的翻译效果。推理代码如下&#xff1a; # 导入模型 if conf.is_peft:model AutoModelForSeq2SeqLM.from_pr…

如何设置端口映射?

端口映射是一种网络技术&#xff0c;通过在网络路由器或防火墙上设置规则&#xff0c;将外部网络请求转发到内部特定设备或服务的端口上。这样可以实现不同地区电脑与电脑、设备与设备、电脑与设备之间的信息远程通信&#xff0c;提供更加便捷的网络连接。 2. 天联组网 天联是…

【环境搭建】(五)Ubuntu22.04安装cuda_11.8.0+cudnn_8.6.0

一个愿意伫立在巨人肩膀上的农民...... 设备配置&#xff1a; 一、安装GCC 安装cuda之前&#xff0c;首先应该安装GCC&#xff0c;安装cuda需要用到GCC&#xff0c;否则报错。可以先使用下方指令在终端查看是否已经安装GCC。 gcc --version 如果终端打印如下则说明已经安装…

K8S容器空间不足问题分析和解决

如上图&#xff0c;今天测试环境的K8S平台出现了一个问题&#xff0c;其中的一个容器报错&#xff1a;Free disk space below threshold. Available: 3223552 bytes (threshold: 10485760B)&#xff0c;意思服务器硬盘空间不够了。这个问题怎么产生的&#xff0c;又怎么解决的呢…

性能优化原则

相关链接&#xff1a;【运行环境】加载资源的形式 性能优化 1 性能优化原则 多使用内存、缓存或其他方法 减少CPU计算量&#xff0c;减少网络加载耗时 &#xff08;适用于所有编程的性能优化----空间换时间&#xff09; 2 从何入手 性能优化-让加载更快 减少资源体积&#x…

neo4j-01

Neo4j是&#xff1a; 开源的&#xff08;社区版开源免费&#xff09;无模式&#xff08;不用预设数据的格式&#xff0c;数据更加灵活&#xff09;noSQL&#xff08;非关系型数据库&#xff0c;数据更易拓展&#xff09;图数据库&#xff08;使用图这种数据结构作为数据存储方…

Edge扩展程序上架流程

代码基本同Chrome扩展&#xff0c;无需改动&#xff0c;具体可以参考文档说明 参考官方文档&#xff0c;注册开发者账号&#xff0c;遇到报错可以参考另一篇文章&#xff0c;Microsoft注册问题 注册完毕后&#xff0c;跳转到 developer dashboard&#xff0c;将左侧导航栏选项…

【案例分享】如何通过甘特图管理项目进度?

我将通过一个实际案例来具体说明我是如何通过甘特图来管理项目进度的。 案例背景&#xff1a; 我负责过一个软件开发项目&#xff1a;一款在线学习APP。项目团队包括项目经理、开发人员、测试人员、UI设计师等多个角色&#xff0c;预计项目周期为6个月。 案例实施过程&…

Redis中的集群(四)

集群 槽指派 CLUSTER ADDSLOTS命令的实现 CLUSTER ADDSLOTS命令接受一个或多个槽作为参数&#xff0c;并将所有输入的槽指派给接收该命令的节点负责: CLUSTER ADDSLOTS <slot> [slot ...]CLUSTER ADDSLOTS命令的实现可以用以下伪代码来表示: def CLUSTER_ADDSLOTS(*…

【MATLAB源码-第5期】基于matlab的BPSK的理论误码率和实际误码率对比仿真。

1、算法描述 BPSK (Binary Phase Shift Keying)-------二进制相移键控。是把模拟信号转换成数据值的转换方式之一&#xff0c;利用偏离相位的复数波浪组合来表现信息键控移相方式。BPSK使用了基准的正弦波和相位反转的波浪&#xff0c;使一方为0&#xff0c;另一方为1&#xf…