首页 > 其他分享 >最短路问题

最短路问题

时间:2024-07-13 18:52:29浏览次数:16  
标签:int 短路 问题 Floyd 1061109567 include addedge

最短路问题

write a short introduce

朴素做法

write something

Code1

Code

多源最短路

比较好于理解与编写的是 Floyd 算法。

Code2

#include <iostream>
#include <iomanip>
#include <string.h>
using namespace std;
int n,m;
int g[105][105];
void addedge(int u,int v,int w)
{
	g[u][v]=w;
	return ;
}
void Floyd()
{
	for(int k=1;k<=n;k++)
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
	return ;
}
int main()
{
	memset(g,0x3f,sizeof g);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		addedge(u,v,w);
		addedge(v,u,w);
	}
	Floyd();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j) cout<<setw(12)<<"0";
			else cout<<setw(12)<<g[i][j];
		}
		cout<<endl;
	}
	return 0;
}
# input
6 5
1 2 3
2 6 8
6 5 1
2 3 5
3 6 1
# output
0           3           8           1061109567  10          9
3           0           5           1061109567  7           6
8           5           0           1061109567  2           1
1061109567  1061109567  1061109567  0           1061109567  1061109567
10          7           2           1061109567  0           1
9           6           1           1061109567  1           0

标签:int,短路,问题,Floyd,1061109567,include,addedge
From: https://www.cnblogs.com/RainCQwQ/p/-/shortest_path

相关文章

  • 探索贪心算法:解决优化问题的高效策略
    贪心算法是一种在每一步选择中都采取当前最佳选择的算法,以期在整体上达到最优解。它广泛应用于各种优化问题,如最短路径、最小生成树、活动选择等。本文将介绍贪心算法的基本概念、特点、应用场景及其局限性。贪心算法的基本概念贪心算法的核心思想是局部最优策略,即在每一步选择......
  • N1盒子挂载磁盘-解决盒子重启后无法自动挂载问题
    MarkdownExampleN1盒子挂载磁盘挂载步骤:step1step2如果提示挂载已存在、就先卸载挂载分区step3回到首页重新挂载step4此时已经挂载成功、但是默认的挂载名是随机的如:usb1-1这样的就会存在一个问题、当N1盒子重启的时候就会不能自动挂载所以要重新修改挂载......
  • CCS工程导入后编译时无法读取头文件的问题
    CCS工程导入后编译时无法读取头文件的问题,主要是由移植之后的文件搜索路径所指向的文件夹不存在导致的。有两种解决办法:①导入工程时将所需要的所有.h、.c以及.lib文件一并打包在工程文件中,复制到Workspace并重新选取搜索路径;②导入工程的电脑安装有C2000WARE,修改CCS中相对路径......
  • 软件安装下载失败,常见问题汇总(微软软件必备运用库)
    文章目录前言一、卸载软件二、激活软件无法打开?三、安装软件必备运用库扩展:win64位操作系统跟win32位操作系统区别之处前言我们在安装激活一些常用的办公软件,如:visio、Matlab、office等等,经常会遇到各种问题,接下来我会介绍一些方法,大家可以尝试看能否解决问题。一、......
  • 常见的 DirectX 修复问题及解决办法
    在我们使用电脑的过程中,DirectX(简称DX)的正常运行对于游戏、多媒体应用以及图形处理等方面都起着至关重要的作用。然而,由于各种原因,DX可能会出现问题,影响我们的使用体验。这时,DX修复应用就成为了解决这些问题的有效工具。一、认识DirectX与常见问题DirectX是一组由微......
  • 动态规划中01背包问题
    动态规划中01背包问题:这记录一下自己的思考和总结:详细讲解:添加链接描述这种题目中有两种解题方法一是二维数组dp[i][j]表示0-i区间背包容量为j的最大价值那么可以有两个方向推出来dp[i][j],不放物品i:由dp[i-1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][......
  • 算法学习笔记(8.3)-(0-1背包问题)
    目录最常见的0-1背包问题:第一步:思考每轮的决策,定义状态,从而得到dp表第二步:找出最优子结构,进而推导出状态转移方程第三步:确定边界条件和状态转移顺序方法一:暴力搜素代码示例:方法二:记忆化搜索时间复杂度取决于子问题数量,也就是O(n*cap)。实现代码如下:方法三:动态规划代......
  • PSIM仿真mosfet驱动问题
    前言在使用PSIM进行仿真的时候遇见了DLL驱动mosfet不成功的问题,搞得头疼心肺炸裂错误情况如下其实起因是我没注意开关器件控制器(多级)有好几个属性当我想仿真实际mosfet的时候,将mosfet设置成了二级模型,但是我的开关器件控制器却没有设置为控制到模型,正确情况部分有截......
  • 关于面向对象的方法并行执行的问题
    LabVIEW的从同一个类实例化的多个对象如何执行各自的方法呢?这几天跟同事讨论到LabVIEW的面向对象编程中,如果我设计的一个类有一个方法比较耗时,那么当我实例化多个对象时,那么这个耗时的方法是怎么执行的呢?是各自并行执行还是,必须等某一个对象的方法调用完,接下来调用第二个对象的该......
  • 解决Microsoft Visual C++ runtime package找不到问题
    使用了Dism++进行电脑清理,不小心选择了下面两个内容:尤其是第二个packagecache绝对不能清空,否则不知道哪个软件就不能运行了,报MicrosoftvisualC++runtime问题.然后再安装各个版本MicrosoftvisualC++redis仍会报同样的问题,死循环了.网上有各种解决方案,有......