ACM程序设计 篇一:ACM图论算法:最短路

2021-01-20 21:25:08 1点赞 0收藏 0评论

Floyd(佛洛依德算法)

三个for暴力循环  O(n^3)

for(ll k=1;k<=节点数;k++)

{

for(ll i=1;i<=节点数;i++)

{

for(ll j=1;j<=节点数;j++)

{

if(a[i][k]+a[k][j]<a[i][j])

{

a[i][j]=a[i][k]+a[k][j];

}

}

}

}

Dijkstra(迪杰斯特拉算法)  O(nlogn)

与Floyd不同,需要暴力枚举出所有边的情况,Dijkstra通过松弛来实现,松弛最著名的理论就是三角形的任意两边之和大于第三边,即每次找一个与起点最近的点,对这个点连接的边进行松弛;

用结构体+链式前向星存边,关键步骤的本质是bfs,可以用C++ STL的堆来进行优化,通常都使用Dijkstra,但是不适合使用在存在负权值的题目,会造成死循环。

tip:优先队列(priority_queue),push进去,会自动按照降序的方式插入,因此需要利用重载符(operator)将降序的方式改成升序

'''

void dij()

{

//默认dis数组的值均为0x3f3f3f3f(最大值)

for(ll i=0;i<=n;i++)

{

dis[i]=inf;

}

dis[s]=0;//起点到起点的距离为0

priority_queue<node> q;

q.push({0,s});

while(!q.empty())

{

ll u=q.top().index;

ll d=q.top().w;

q.pop();

if(dis[u]<d)continue;

//如果队列里面的这个点到起点的距离比dis数组里面当前这个点到起点的距离大,则continue

//也可以用vis数组代替

//以下为链式前向星,对每一个点进行遍历

for(ll i=head[u];i!=-1;i=e[i].next)

{

ll v=e[i].to;

if(dis[v]>e[i].w+dis[u])

{

dis[v]=e[i].w+dis[u];

q.push({dis[v],v});

}

}

}

}

'''

向我的偶像迪杰斯特拉致敬

ACM图论算法:最短路


展开 收起

Apple 苹果 iPhone 11 4G手机

Apple 苹果 iPhone 11 4G手机

4199元起

Apple 苹果 iPhone XR 4G手机

Apple 苹果 iPhone XR 4G手机

3853元起

小米米家飞利浦台灯Lite护眼灯学生学习阅读卧室宿舍书桌台灯床头灯保视力

小米米家飞利浦台灯Lite护眼灯学生学习阅读卧室宿舍书桌台灯床头灯保视力

79元起

OPPO Enco Air灵动版 入耳式真无线蓝牙耳机

OPPO Enco Air灵动版 入耳式真无线蓝牙耳机

149元起

包纳 数据线收纳包充电器ipad平板保护套耳机线双层防水抗震U盘U盾

包纳 数据线收纳包充电器ipad平板保护套耳机线双层防水抗震U盘U盾

15.9元起

Jeefanco杰梵客 咬线器数据线保护套充电线苹果华为vivo专用oppo充电器小米iphone手机防折断绕线器接头可爱缠绕贴纸 白熊猫A

Jeefanco杰梵客 咬线器数据线保护套充电线苹果华为vivo专用oppo充电器小米iphone手机防折断绕线器接头可爱缠绕贴纸 白熊猫A

暂无报价

GARMIN 佳明 Venu 2S智能运动时尚腕表 玫瑰金

GARMIN 佳明 Venu 2S智能运动时尚腕表 玫瑰金

2980元起

Fujifilm/富士 X100F 旁轴数码相机 x100f X100f

Fujifilm/富士 X100F 旁轴数码相机 x100f X100f

6599元起

益衡Enhance7145B1 FLEX小1U电源 功率450W显卡6+2PIN

益衡Enhance7145B1 FLEX小1U电源 功率450W显卡6+2PIN

450元起

Sound Blaster JAM V2 黑色

Sound Blaster JAM V2 黑色

399元起

飞傲(FiiO) FH5s两圈两铁混合四单元重低音可换线发烧HIFI有线入耳式耳机 银色

飞傲(FiiO) FH5s两圈两铁混合四单元重低音可换线发烧HIFI有线入耳式耳机 银色

1699元起

联想 Y400 Y430P Y410P Y400P Y400N Y410N IFI ISE笔记本键盘

联想 Y400 Y430P Y410P Y400P Y400N Y410N IFI ISE笔记本键盘

65元起

AJAZZ 黑爵 镖人定制机械键盘 蓝牙键盘 双模键盘 热升华键帽 蓝牙5.0 多设备 白光 电脑笔记本办公 奶黄轴

AJAZZ 黑爵 镖人定制机械键盘 蓝牙键盘 双模键盘 热升华键帽 蓝牙5.0 多设备 白光 电脑笔记本办公 奶黄轴

499元起

【特惠】Smartisan锤子坚果快速充电头18w安卓通用手机充电器

【特惠】Smartisan锤子坚果快速充电头18w安卓通用手机充电器

29元起

熊猫 PX27QA2 27英寸 2K显示器 IPS硬屏 75Hz游戏办公 电脑显示屏幕 超薄微边框 HDMI超清电竞液晶屏 PS5

熊猫 PX27QA2 27英寸 2K显示器 IPS硬屏 75Hz游戏办公 电脑显示屏幕 超薄微边框 HDMI超清电竞液晶屏 PS5

999元起

BGVP NS9 星空蓝 官方标配

BGVP NS9 星空蓝 官方标配

999元起
0评论

发表评论请 登录
评论举报

请选择举报理由

相关好价推荐
查看更多好价

相关文章推荐

更多精彩文章
更多精彩文章

drophair

一个acm打铁玩家

关注 打赏
相关好价
最新文章 热门文章
0
扫一下,分享更方便,购买更轻松