找回密码
 中文实名注册
查看: 287|回复: 1

朴素dijkstra(没使用链式前向星,会卡常)

[复制链接]

5

主题

125

帖子

2185

积分

金牌会员

Rank: 6Rank: 6

积分
2185
发表于 2024-8-9 18:35:13 | 显示全部楼层 |阅读模式
本帖最后由 周星宇 于 2024-8-9 18:52 编辑

[C++] 纯文本查看 复制代码
#include <bits/stsc++.h>      
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int n, m;
// 稠密图,邻接矩阵存图
int g[N][N];
// 表示每个点当前,从1号点走到他自己的最短距离
int dist[N];
// 每个点的最短路是否已经确定
int st[N];
int dijkstra(){
   // 初始化距离
   memset(dist, 0x3f, sizeof dist);
   dist[1] = 0;
   // 有n个点所以要进行n次 迭代
   for (int i = 0; i < n; i++){
    	int t = -1;
    	// 找到一个 距离源点最近的点,且这个点还没有确定最短路径st[j]=fasle 
    	for (int j = 1; j <= n; j++){
        	// 当前这个点还没有确定最短路径
        	// 且
        	// 源点到当前这个点的距离是最短的
        	if (st[j] == false && (t == -1 || dist[t] > dist[j])){
           		 // 找到了这个点j
            	t = j;
        	}
    	}
    	// 把t加到st里面去,标记这个点已经确定最短距离
    	st[t] = true;
    	// 用当前这个点更新其他点的距离
    	for (int j = 1; j <= n; j++){
        	// 1到j这个点的距离,和1到t再从t到j这个点的距离比大小
        	dist[j] = min(dist[j], dist[t] + g[t][j]);
    	}
    }
	// 1和n不联通
   if (dist[n] == INF){
    return -1;
   }else{
    return dist[n];
   }
 
}
int main(){
   cin >> n >> m;
   memset(g, 0x3f, sizeof g);
   for(int i=1;i<=m;i++){
    	int a, b, c;
    	cin >> a >> b >> c;
    	// 处理重边,两条边只保留一条距离最短的边 
    	g[a][b] = min(g[a][b], c);
   }cout<<dijkstra();
   return 0;
}
回复

使用道具 举报

15

主题

87

帖子

725

积分

高级会员

Rank: 4

积分
725
发表于 2024-9-21 10:24:15 | 显示全部楼层
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 中文实名注册

本版积分规则

小黑屋|东台市机器人学会 ( 苏ICP备2021035350号-1;苏ICP备2021035350号-2;苏ICP备2021035350号-3 )

GMT+8, 2024-10-12 18:28 , Processed in 0.041803 second(s), 28 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表