web analytics

最短路 从基础题到变式题 集合

写一篇关于图论-最短路相关的习题集合。

从基础到变式相关吧

一 模板

首先是最简单的Dijkstra-Heap和SPFA的模板题

https://www.luogu.com.cn/problem/P3371

Dijkstra-Heap版本

SPFA版本

二 基本题

1>P1339 [USACO09OCT]热浪Heat Wave

2>P2984 [USACO10FEB]给巧克力Chocolate Giving

3>P3905 道路重建

4>P1144 最短路计数

5>P1828 香甜的黄油 Sweet Butter

三 负环相关

1>P2850 [USACO06DEC]虫洞Wormholes

 

四 反图相关

1>P1073 最优贸易

 

五 分层图相关

1>P1073 最优贸易

2>P4568 [JLOI2011]飞行路线

3>P1948 [USACO08JAN]电话线Telephone Lines

 

六 差分约束系统

1>P3275 [SCOI2011]糖果