解题思路:,套用一个没有经过堆优化版本的Dijstra算法模板
注意事项:
参考代码:
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=510; int g[N][N]; //稠密图用邻接矩阵存储 int dist[N]; //dist[i]表示i节点到源点(下标为u的节点)的距离 bool st[N]; //st[i]用于标记i节点的最短路是否确定,若确定st[i]=true int n,m; void Dijkstra(int u) //该模板求节点编号为u的点到图中其他的点的最短距离, { memset(dist,0x3f,sizeof dist); dist[u]=0; //除u号节点外,其他均初始为无穷大 for(int i=0;i<n;i++) //n次迭代,每次寻找不在st中距离最近的点t { int t=-1;//t是用来存储当前所访问的点 因为点的编号是从1-n t=-1即为初始化 for(int j=0;j<n;j++) //这一步是在遍历遍历 dist 数组,找到一个节点,这个节点是:没有确定最短路径的节点中距离源点最近的点。 if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j; st[t]=true; //将t加到s中 for(int j=0;j<n;j++) //用t更新其他点的距离 if(g[t][j]!=0) dist[j]=min(dist[j],dist[t]+g[t][j]); } } int main() { scanf("%d%d",&n,&m); memset(g,0x3f,sizeof g); int temp; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { scanf("%d",&temp); if(temp!=0) g[i][j]=temp; } } Dijkstra(m); for(int i=0;i<n;i++) { if(i==m) continue; if(dist[i]==0x3f3f3f3f) printf("-1 "); else printf("%d ",dist[i]); } printf("\n"); }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:711 |
简单的a+b (C语言代码)浏览:817 |
打印十字图 (C语言代码)浏览:2710 |
DNA (C语言代码)浏览:394 |
sizeof的大作用 (C语言代码)浏览:1028 |
模拟计算器 (C语言代码)浏览:2300 |
输出九九乘法表 (C语言代码)浏览:1048 |
小O的乘积 (C语言代码)浏览:1014 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:521 |
简单的a+b (C语言代码)浏览:564 |