Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"CodeForces-20C\":[\"Dijkstra?\",34303,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/20\\\"\\u003eCodeforces Alpha Round 20 (Codeforces format)\\u003c/a\\u003e\"],\"洛谷-P1993\":[\"小 K 的农场\",15874,null],\"洛谷-P4568\":[\"飞行路线\",16634,\"JLOI2011\"],\"洛谷-P4822\":[\"冻结\",5387,\"BJWC2012\"],\"洛谷-P2446\":[\"大陆争霸\",2432,\"SDOI2010\"],\"CodeForces-1887B\":[\"Time Travel\",2683,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1887\\\"\\u003eCodeforces Round 905 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P1576\":[\"最小花费\",16532,null],\"洛谷-P3632\":[\"寻路\",194,\"APIO2011\"],\"CodeForces-144D\":[\"Missile Silos\",4291,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/144\\\"\\u003eCodeforces Round 103 (Div. 2)\\u003c/a\\u003e\"],\"洛谷-P1119\":[\"灾后重建\",28004,null],\"洛谷-P2648\":[\"赚钱\",1968,null],\"洛谷-P1613\":[\"跑路\",14410,null],\"CodeForces-1005F\":[\"Berland and the Shortest Paths\",1732,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1005\\\"\\u003eCodeforces Round 496 (Div. 3)\\u003c/a\\u003e\"],\"洛谷-P1938\":[\"Job Hunt S\",4058,\"USACO09NOV\"],\"CodeForces-449B\":[\"Jzzhu and Cities\",9544,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/449\\\"\\u003eCodeforces Round 257 (Div. 1)\\u003c/a\\u003e\"],\"CodeForces-715B\":[\"Complete The Graph\",2983,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/715\\\"\\u003eCodeforces Round 372 (Div. 1)\\u003c/a\\u003e\"],\"CodeForces-786C\":[\"Till I Collapse\",2740,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/786\\\"\\u003eCodeforces Round 406 (Div. 1)\\u003c/a\\u003e\"],\"洛谷-P2294\":[\"狡猾的商人\",7627,\"HNOI2005\"],\"洛谷-P6175\":[\"无向图的最小环问题\",7384,null],\"洛谷-P5764\":[\"新年好\",2191,\"CQOI2005\"],\"洛谷-P1144\":[\"最短路计数\",40095,null],\"洛谷-P5960\":[\"差分约束\",18301,\"模板\"],\"洛谷-P1462\":[\"通往奥格瑞玛的道路\",19499,null],\"洛谷-P5767\":[\"最优乘车\",3212,\"NOI1997\"],\"洛谷-P1522\":[\"牛的旅行 Cow Tours\",11674,\"USACO2.4\"],\"洛谷-P5304\":[\"旅行者\",3507,\"GXOI/GZOI2019\"],\"洛谷-P4779\":[\"单源最短路径(标准版)\",125526,\"模板\"],\"CodeForces-33B\":[\"String Problem\",4811,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/33\\\"\\u003eCodeforces Beta Round 33 (Codeforces format)\\u003c/a\\u003e\"],\"洛谷-P3905\":[\"道路重建\",8806,null],\"CodeForces-1650G\":[\"Counting Shortcuts\",2423,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1650\\\"\\u003eCodeforces Round 776 (Div. 3)\\u003c/a\\u003e\"],\"洛谷-P5905\":[\"全源最短路(Johnson)\",7419,\"模板\"],\"洛谷-P1828\":[\"香甜的黄油 Sweet Butter\",12162,\"USACO3.2\"],\"洛谷-P2939\":[\"Revamping Trails G\",6688,\"USACO09FEB\"],\"CodeForces-208C\":[\"Police Station\",2182,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/208\\\"\\u003eCodeforces Round 130 (Div. 2)\\u003c/a\\u003e\"],\"CodeForces-1442C\":[\"Graph Transpositions\",1593,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1442\\\"\\u003eCodeforces Round 681 (Div. 1, based on VK Cup 2019-2020 - Final)\\u003c/a\\u003e\"],\"CodeForces-1163F\":[\"Indecisive Taxi Fee\",911,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1163\\\"\\u003eCodeforces Round 558 (Div. 2)\\u003c/a\\u003e\"],\"CodeForces-545E\":[\"Paths and Trees\",4798,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/545\\\"\\u003eCodeforces Round 303 (Div. 2)\\u003c/a\\u003e\"],\"洛谷-P3371\":[\"单源最短路径(弱化版)\",123368,\"模板\"],\"洛谷-P1073\":[\"最优贸易\",22316,\"NOIP2009 提高组\"],\"洛谷-P3275\":[\"糖果\",10655,\"SCOI2011\"],\"洛谷-P1396\":[\"营救\",23385,null]}","joined":false,"groups":{}},"managingGroups":{},"author":"Exile_code","updateTime":1712459635000,"title":"进阶图论(最短路系列)","dislikeCnt":0,"content":"1.单源最短路\n(1)视频学习\n[D02 单源正权图最短路 Dijkstra与堆优化](https://www.bilibili.com/video/BV1Ya411L7gb?vd_source\u003daffb7616e4b4bb9edc2495f2da9d64e9)\n[D03 单源负权图最短路 Bellman-Ford 算法 SPFA 算法](https://www.bilibili.com/video/BV1uL4y1N7Tb?vd_source\u003daffb7616e4b4bb9edc2495f2da9d64e9)\n[D04 多源最短路 Floyd 算法](https://www.bilibili.com/video/BV1u34y1575Y?vd_source\u003daffb7616e4b4bb9edc2495f2da9d64e9)\n[D05 多源最短路 Johnson 算法](https://www.bilibili.com/video/BV1KS4y1q7Kc?vd_source\u003daffb7616e4b4bb9edc2495f2da9d64e9)\n(2)文章学习\n[多数最短路算法分析](https://www.luogu.com/article/qrelo71t)\n[差分约束的分析文章](https://www.luogu.com/article/aigajvbq)\n(3)题目狂刷\n[problem:洛谷-P3371]【模板】单源最短路径(弱化版)\n[problem:洛谷-P4779]【模板】单源最短路径(标准版 )\n[problem:CodeForces-20C]【模板】1900 输出路径\n[problem:洛谷-P1576]黄(黄题一半是一步转化即可,重点是熟悉板子)\n[problem:洛谷-P5767]黄(考察一种神奇的n方建图方式)\n[problem:洛谷-P5764]黄(全排列暴力枚举,建议使用全排列函数next_permutation)\n[problem:洛谷-P1938]黄(套模板,点权转边权)\n[problem:洛谷-P1396]黄(套模板)\n[problem:洛谷-P3905]黄(套模板,考察存边的技巧)\n[problem:洛谷-P2648]黄(套模板,跟Job Hunt S一样)\n[problem:洛谷-P1144]绿(套模板,记录路径的转化方式,类似拓扑图dp的更新方式)\n[problem:洛谷-P1828]绿(套模板,暴力枚举,注意图可能不连通)\n[problem:洛谷-P1462]绿(二分+迪杰斯特拉)\n[problem:洛谷-P5304]蓝(非常经典的双集合枚举方式)(注:如果一直TLE,试着换成全局变量数组试试)\n[problem:CodeForces-144D]1900(分类讨论)\n[problem:CodeForces-1887B]1900(边集映射的模拟)\n[problem:CodeForces-545E]2000(迪杰斯特拉出队先后性质深度刨析题目)\n[problem:CodeForces-449B]2000(最短路删边的影响思考题)\n[problem:CodeForces-1650G]2100\n[problem:CodeForces-1005F]2100\n[problem:洛谷-P2446]紫\n[problem:洛谷-P3632]紫\n[problem:CodeForces-786C]2300 \n[problem:CodeForces-715B]2300 \n[problem:CodeForces-1442C]2400 \n[problem:CodeForces-1163F]3000 \n2.多源最短路\n[problem:洛谷-P5905]绿【模板】Johnson\n[problem:洛谷-P6175]黄 floyd插点的枚举策略\n[problem:洛谷-P1613]绿 倍增算法+floyd\n[problem:CodeForces-33B]1800 floyd枚举转化\n[problem:洛谷-P1522]绿\n[problem:洛谷-P1119]绿 floyd的枚举点的意义\n[problem:CodeForces-208C]1900(路径记录与思维枚举)\n3.分层最短路\n[problem:洛谷-P1073]绿(分层图最短路、tarjan缩点后dp乱搞都行)\n[problem:洛谷-P4822]绿\n[problem:洛谷-P2939]蓝\n[problem:洛谷-P4568]蓝\n4.差分约束\n[problem:洛谷-P5960]绿 【模板】\n[problem:洛谷-P2294]绿(差分约束建边方式的集大成者)\n[problem:洛谷-P1993]绿\n[problem:洛谷-P3275]蓝","threadId":187822,"likeCnt":1,"createTime":1711246917000,"isWorkbook":true,"viewCnt":316,"openness":2,"fav":false,"id":4748,"trustable":false}