SDUTACM 图结构练习——最短路径

以你之姓@ 2022-09-25 06:27 169阅读 0赞

## 题目描述 ##

给定一个带权无向图，求节点1到节点n的最短路径。

## 输入 ##

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表节点个数和边的个数。(n<=100)

剩下m行每行3个正整数a b c，代表节点a和节点b之间有一条边，权值为c。

## 输出 ##

每组输出占一行，仅输出从1到n的最短路径权值。（保证最短路径存在）

## 示例输入 ##

3 2
    1 2 1
    1 3 1
    1 0

## 示例输出 ##

1
    0

## 提示 ##

#include<stdio.h>
    #include<stdlib.h>
    #define max 65535
    int weight[110][110];
    void main()
    {
    	int m,n;
    	while(scanf("%d%d",&m,&n)!=EOF)
    	{
    		int i,j;
    		int k,u,v,w;
    		for(i=1;i<=m;i++)
    		{
    			for(j=1;j<=m;j++)
    				weight[i][j]=max;
    			weight[i][i]=0;
    		}
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d%d%d",&u,&v,&w);
    			if(weight[u][v]>w)
    			{
    				weight[u][v]=w;
    				weight[v][u]=w;
    			}
    		}

弗洛伊德算法：    for(k=1;k<=m;k++)
    		    for(i=1;i<=m;i++)
    				for(j=1;j<=m;j++)
    				{
    					if(weight[i][j]>(weight[i][k]+weight[k][j]))
    						weight[i][j]=weight[i][k]+weight[k][j];
    				}
    	    printf("%d\n",weight[1][m]);
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构之图结构解最短路径

图结构 1. 邻接矩阵：可以理解为一个二维数组，即一个正方形的图。例如：动态规划解LCS最长公共子序列，实现代码见：[https://blog.csdn.net/u01

不念不忘少年蓝@/ 2024年02月19日 21:20/ 0 赞/ 47 阅读

相关 SDUTACM 图结构练习——最小生成树

题目描述有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其

た入场券/ 2022年09月25日 07:22/ 0 赞/ 182 阅读

相关 SDUTACM 图结构练习——最短路径

题目描述给定一个带权无向图，求节点1到节点n的最短路径。输入输入包含多组数据，格式如下。第一行包括两个整数n m，代表节点个数和边的个数。(n<=100

以你之姓@/ 2022年09月25日 06:27/ 0 赞/ 170 阅读

相关图结构练习——最短路径

图结构练习——最短路径 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给定一个带权

矫情吗；*/ 2022年08月18日 02:28/ 0 赞/ 169 阅读

相关图结构练习——最短路径

图结构练习——最短路径 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Pro

偏执的太偏执、/ 2022年07月13日 22:40/ 0 赞/ 160 阅读

相关图结构练习——最短路径

Problem Description 给定一个带权无向图，求节点1到节点n的最短路径。 Input 输入包含多组数据，格式如下。第一行包括两个整数n m，代

清疚/ 2022年07月12日 07:50/ 0 赞/ 179 阅读

相关图结构练习——最短路径

Problem Description 给定一个带权无向图，求节点1到节点n的最短路径。 Input 输入包含多组数据，格式如下。第一行包括两个整数n m，代

忘是亡心i/ 2022年07月12日 07:50/ 0 赞/ 162 阅读

相关图结构练习——最短路径（Dijkstra算法）

字节跳动校招内推码: C4BDSMC 投递链接: https://job.toutiao.com/s/J691fRK 内推交流QQ群：104917572

迷南。/ 2022年07月10日 15:58/ 0 赞/ 227 阅读

相关最短路径（图）

Dijkstra算法 Dijkstra算法为求带权图中从一个顶点（此处假设为Vo）到其它各顶点的最短路径，按路径长度递增的次序产生最短路径，假设所有权值非负。储存结构

矫情吗；*/ 2022年06月02日 03:59/ 0 赞/ 222 阅读

相关数据结构——图——最短路径

Dijkstra单源最短路径算法给定一个带权[有向图][Link 1]G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他

系统管理员/ 2022年04月12日 02:08/ 0 赞/ 247 阅读