少年Q

用户名：yin19990129

访问量：25366

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

53.最短路练习-题解(C++代码)只做最好的思路！
浏览：164

[传智杯]软件工程实习（C++描述）只做最好的思路！
浏览：380

[传智杯]程序员节发橙子（C++描述）只做最好的思路！
浏览：487

你可能喜欢

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

53.最短路练习-题解(C++代码)只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-04-20 17:10:21 浏览：164　|　评论：0　

原题链接：最短路练习

最短路问题是个经典的老问题了，一般有Dijkstra\Floyd\Spfa三种解法，具体不多阐述。。。时间长了，之前基础学的不咋地，所以碰到老问题又跪了。mmp...555.。。
在复习完基础知识后，根据邻接矩阵（可以自己画出矩阵意义下的map），这里参考老师傅的意见，利用Dijkstra算法，模拟出最短路径，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[55][55],dis[55],visited[55];
int inf=10000,n;
void dijkstra(){
	//初始化，dis[]为最大，visited[]为最小
	memset(dis,inf,sizeof(dis));
	memset(visited,0,sizeof(visited));
	dis[1]=0;//到初始点的距离为0
	for(int i=1;i<=n;i++){
		int u,mi=inf;//u为dis[]中最小点的编号 
		//寻找此时dis[]中的最小值
		for(int j=1;j<=n;j++){
			if(dis[j]<mi&&visited[j]==0){
				mi=dis[j];
				u=j;
			}
		} 
		//找到dis[]最小的点，加入集合，更新与其相连的点的dis值
		visited[u]=1;//在路径中加入该点 
		for(int j=1;j<=n;j++){
			dis[j]=min(dis[j],dis[u]+a[u][j]);
		} 
	} 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	dijkstra();
	cout<<dis[n];
	return 0;
}
```
对最短路问题再次深入分析后，发现对于这题来说，只要抓住问题的本质描绘出邻接矩阵意义下的map路径最小值，即使不用经典算法也是可以解决的，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	int a[n+1][n+1];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		if(a[i][k]+a[k][j]<a[i][j]){
			a[i][j]=a[i][k]+a[k][j];
		}
	}
	cout<<a[1][n]<<endl;
	return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

少年Q

TA的其他文章

你可能喜欢

C二级辅导-计负均正（C++代码）

倒杨辉三角形（C语言代码）

C二级辅导-计负均正（C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

53.最短路练习-题解(C++代码)只做最好的思路！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

三角形（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

整除的尾数（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

少年Q

TA的其他文章

你可能喜欢

C二级辅导-计负均正 （C++代码）

倒杨辉三角形 （C语言代码）

C二级辅导-计负均正 （C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

53.最短路练习-题解(C++代码)只做最好的思路！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

三角形 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

蓝桥杯历届试题-翻硬币 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

整除的尾数 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C二级辅导-计负均正（C++代码）

倒杨辉三角形（C语言代码）

C二级辅导-计负均正（C语言代码）

　　评论区

三角形（C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）

整除的尾数（C语言代码）

C语言训练-斐波纳契数列（C语言代码）