图结构练习——最短路径

偏执的太偏执、 2022-07-13 22:40 114阅读 0赞

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

Time Limit: 1000MS  Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

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

#### Input ####

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

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

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

#### Output ####

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

#### Example Input ####

3 2
    1 2 1
    1 3 1
    1 0

#### Example Output ####

1
    0

#include <stdio.h>
    #define INF 0x3f3f3f
    int map[2333][2333];
    int dis[2333];
    void Fory(int n)
    {
    	int i,j,k;
    	for(i=0;i<=n;i++)
    	{
    		for(j=0;j<=n;j++)
    		{
    			for(k=0;k<=n;k++)
    			{
    				if(map[j][k]>map[j][i]+map[i][k])
    				{
    					map[j][k]=map[j][i]+map[i][k];
    				}
    			}
    		}
    	}
    }
    int main()
    {
    	int n,m,i,j,a,b,c;
    	while(~scanf("%d%d",&n,&m))
    	{
    		for(i=0;i<=n;i++)
    		{
    			for(j=0;j<=n;j++)
    			{
    				if(i!=j)
    				{
    					map[i][j] = INF; 
    				}
    				else
    				{
    					map[i][j] = 0;
    				}
    			}
    		}
    		for(i=0;i<m;i++)
    		{
    			scanf("%d%d%d",&a,&b,&c);
    			map[a][b] = map[b][a] = c;
    		}
    		Fory(n);
    		printf("%d\n",map[n][1]);
    	}
    	return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1925/pid/2143.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1925/pid/2143.html

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关最短路径（图）

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

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 1 引言最短路径问题一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域

﹏ヽ暗。殇╰゛Y/ 2022年04月24日 05:52/ 0 赞/ 200 阅读

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

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

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

相关数据结构【图】—025最短路径距离

/\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\迪杰斯卡特（Dijstra）\\\\\\\\\\\\\\\\\\\\\\\\\\/ 讲解： 1、Dijk

刺骨的言语ヽ痛彻心扉/ 2022年01月05日 23:57/ 0 赞/ 254 阅读