无名

P4779 【模板】单源最短路径（标准版）

Jacken @ 2023-08-29 18:03:41

这题能用spfa吗

我spfa才十六分！！！！ ………………………………

by IsHPDuwu @ 2023-08-29 18:04:36

题目背景

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

$\text{Ag} \rightarrow \text{Cu}$； 最终，他因此没能与理想的大学达成契约。 小 F 衷心祝愿大家不再重蹈覆辙。

by IsHPDuwu @ 2023-08-29 18:04:54

@Jacken 广为人知的算法->spfa

by IsHPDuwu @ 2023-08-29 18:05:12

@Jacken spfa去弱化版

by Jacken @ 2023-08-29 18:06:56

那为啥还要学spfa啊？迪杰斯特拉都比他快

by Jacken @ 2023-08-29 18:07:44

我迪杰斯特拉都一百了（之前）

by cjh20090318 @ 2023-08-29 18:11:17

@Jacken SPFA 可以跑负权，但是 Dijkstra 不行。

by Eleveslaine @ 2023-08-29 18:12:00

你说得对，所以我不会 spfa。

by Jacken @ 2023-08-29 18:16:20

哦

by Tou_ch @ 2023-08-29 18:21:53

查了下原来spfa就是Bellman-Ford啊（）

我之前一直不知道spfa是什么（

by AC_CSP @ 2023-09-02 12:26:28

@Tou_ch spfa不是Bellman-Ford的队列优化吗，随机图跑得快很多

|