- C24zhengfujia's blog
图论最短路
-
C24zhengfujia
LV 10
@
2025-4-26 21:02:30
做了那么多最短路
写了那么多shit
那么，请拿上来自nPr123f的免费车票，一起往下翻~
图论最短路题型大类介绍及题单
裸BFS （好像不应该出现在这里）
| ID | 题目 |
|---|---|
| 862 | #A1377. 最优乘车(travel) |
Dijkstra（单源点多终点，边权非负）
| ID | 题目 |
|---|---|
| 1065 | #P3371. 【模板】单源最短路径（弱化版） |
| 1064 | #P4779. 【模板】单源最短路径（标准版） |
| 829 | #A1344. 【例4-4】最小花费 |
| 1087 | #P1629. 邮递员送信 |
Bellman-Ford、SPFA（单源点多终点，边权任意）
| ID | 题目 |
|---|---|
| 1081 | #P3385. 【模板】负环 |
| 1083 | #P1807. 最长路（大于小于反过来就行） |
| 1088 | #1088. 拉近距离 |
Floyd（多源点多终点，边权任意）
| ID | 题目 |
|---|---|
| 827 | #A1342. 【例4-1】最短路径问题【Floyd模板】 （nPr123f: 史！纯史！） |
| 1087 | #P1629. 邮递员送信 |