kuangbin最短路专题链接：https://cn.vjudge.net/contest/231324
写题解的就是比较好的题了
| 1 / 3 | POJ 2387 | Til the Cows Come Home |
| 1 / 1 | POJ 2253 | Frogger 找间隔最小的路径 |
| 1 / 6 | POJ 1797 | Heavy Transportation |
| 1 / 1 | POJ 3268 | Silver Cow Party |
| 1 / 1 | POJ 1860 | Currency Exchange |
| 1 / 1 | POJ 3259 | Wormholes |
| 1 / 1 | POJ 1502 | MPI Maelstrom |
| 1 / 4 | POJ 3660 | Cow Contest 传递闭包的应用 |
| 1 / 7 | POJ 2240 | Arbitrage 判断是否存在可循环圈 |
| 1 / 6 | POJ 1511 | Invitation Cards 往返最短路 |
| 1 / 3 | POJ 3159 | Candies 差分约束 |
| 0 / 0 | POJ 2502 | Subway 输入的处理很折磨人 |
| 1 / 1 | POJ 1062 | 昂贵的聘礼 |
| 1 / 3 | POJ 1847 | Tram |
| 1 / 9 | LightOJ 1074 | Extended Traffic 注意连通性 |
| 0 / 4 | HDU 4725 | The Shortest Path in Nya Graph 超时 |
| 1 / 9 | HDU 3416 | Marriage Match IV 最短路+最大流 找各最短路的所有边 |
| 1 / 4 | HDU 4370 | 0 or 1 考虑连通性 |
| 1 / 5 | POJ 3169 | Layout 差分约束 |
| 用途 | 原理 | 例题 |
| 正权单源最短路 | 略 | 略 |
| 往返最短路 | 把边反向，再跑一次最短路 | POJ-1511 Invitation Cards, CF EducationalRound40-D Fight Against Traffic |
| 差分约束系统 | 不等式各变量系数为一时，可看做满足最短路的条件 | POJ-3159 Candies, POJ-3169 Layout |
| 找各节点间隔最小的路径 | 类似动态规划，转移前一节点的间隔状态 | POJ-2253 Frogger |
| 找有限制的最短路 | 类似动态规划，转移前一节点的限制状态，在松驰前做判断 | POJ-1062 昂贵的聘礼 |
| 判断某条边是否被最短路包含 | 求往返最短路，满足distA[from]+distB[to]+e.dist==distA[B] | CF EducationalRound40-D Fight Against Traffic, HDU-3416 Marriage Match IV |
| 找AB间各路径最大边权的最小值的最小值 | 松驰操作改为取最小/最大即可 | UVA-10048 Audiophobia |
| 用途 | 原理 | 例题 |
| 判断是否存在可循环圈 | 略 | POJ-2240 Arbitrage |
| 含负权的单源最短路 | 略 | 略 |
| 用途 | 原理 | 例题 |
| 含负权的多源最短路 | 虽然不能判断可循环圈，但不存在的情况下是最短路？ | 略 |
| 有向图传递闭包 | 就是间接可达 | UVA-247 Calling Circles, POJ-3660 Cow Contest |
| 找AB间各路径最大边权的最小值的最小值 | 松驰操作改为取最小/最大即可 | UVA-10048 Audiophobia |
每次做题时要考虑的
原文：https://www.cnblogs.com/tanglizi/p/9159484.html