解题思路:
注意事项:
参考代码:
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=55; int g[N][N]; //为稠密阵所以用邻接矩阵存储 int dist[N]; //用于记录每一个点距离节点编号为u的节点的距离 bool st[N]; //用于记录该点的最短距离是否已经确定 int n; void Dijkstra(int u) { memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大 Dijkstra函数结束后d[i]还是无穷大说明下下标为u的点无法到达i号节点 dist[u]=0; //u号点到自身的距离为0 for(int i=0;i<n;i++) //有n个点所以要进行n次 迭代 { int t=-1; //t存储当前访问的点 for(int j=0;j<n;j++) //这里的j代表的是从编号为0号点开始 if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; st[t]=true; for(int j=0;j<n;j++) //依次更新每个点所到相邻的点路径值 dist[j]=min(dist[j],dist[t]+g[t][j]); } } int main() { scanf("%d",&n); memset(g,0x3f,sizeof g); //初始化图 因为是求最短路径 //所以每个点初始为无限大 for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&g[i][j]); Dijkstra(0); //求0号点到其他点的距离,调用就可 if(dist[n-1]==0x3f3f3f3f) printf("-1\n"); //如果第n个点路径为无穷大即不存在最低路径 else printf("%d\n",dist[n-1]); }
0.0分
1 人评分
A+B for Input-Output Practice (IV) (C语言代码)浏览:451 |
简单的a+b (C语言代码)浏览:524 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:526 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:504 |
DNA (C语言代码)浏览:746 |
小O的数字 (C++代码)浏览:757 |
众数问题 (C语言代码)浏览:622 |
用getchar()函数接收字符,正序输入为什么会倒序输出浏览:741 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:502 |
成绩转换 (C语言代码)浏览:586 |