最短路文章列表
[luoguP3110] [USACO14DEC]驮运Piggy Back（SPFA || BFS）
传送门 以 1，2，n 为起点跑3次 bfs 或者 spfa 那么 ans = min(ans, dis[1][i] * B + dis[2][i] * E + dis[3][i] * P) (1 =...spfa,bfs,最短路
[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）
传送门 因为答案满足单调性，所以看到这个题，第一反应是二分，但是总是WA，也没有超时。 看了题解，，，，，， 这题刚开始很多人会想到二分，二分答案，然后看看是否能绕过所有信号塔，但是，这样写明显超时，...二分,并查集,最短路,kruskal,dijkstra
[luoguP1849] [USACO12MAR]拖拉机Tractor（spfa）
传送门 神奇的spfa #include queue#include cstdio#include cstring#include iostream#define N 1010#define max(...spfa,最短路
[luoguP1772] [ZJOI2006]物流运输（DP + spfa）
传送门 预处理cost[i][j]表示从第i天到第j天起点到终点的最短距离 f[i]表示前i天到从起点到终点的最短距离 f[0] = K f[i] = min(f[i], f[j 1] + cost[...DP,spfa,最短路
[luoguP2622] 关灯问题II（状压最短路）
传送门 本以为是状压DP，但是有后效性。 所以写一手状压spfa #include queue#include cstdio#include cstring#include iostream#defi...spfa,最短路
[CODEVS1912] 汽车加油行驶问题（分层图最短路）
传送门 吐槽：神tm网络流 dis[i][j][k] 表示到 (i, j) 还有 k 油的最优解 然后跑spfa，中间分一大堆情况讨论 1.当前队头还有油 1.目标点有加油站——直接过去 2.目标点每...最短路,spfa
[CODEVS1911] 孤岛营救问题（分层图最短路）
传送门 吐槽：神tm网络流。。。 用持有的钥匙分层，状态压缩，用 2 进制表示持有的钥匙集合。 dis[i][j][k] 表示持有的钥匙集合为 k，到达点 (i, j) 的最短路径。 分层图的最短路听...最短路,spfa
[luoguP2761] 软件补丁问题（状压最短路）
传送门 n = 20 很小 所以可以状态压缩 然后因为可能存在环，所以不能DP 那么就用spfa找最短路 被位运算坑了，不清楚优先级一定要加括号 ——代码 1 #include queue 2 #in...spfa,最短路
[POJ3463] Sightseeing（次短路 Heap + Dijkstra）
传送门 用dijkstra比较好，spfa可能有的重复 dis[x][2]:dis[x][0]表示起点到x的最短路、dis[x][1]表示起点到x的次短路； tot[x][2]:tot[x][0]表示...最短路,stl,堆,dijkstra
[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）
传送门 题意 N个点M条边的有向图 每个点有点权 从某一个结点出发 问能获得的最大点权和 一个点的点权最多被计算一次 N=500000 M=500000 思路 先tarjan缩点，然后就形成一个dag...DP,最短路,dfs,spfa,stl
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化