spfa文章列表
[luoguP3953] 逛公园（DP + spfa）
传送门 看到求方案数，应该很容易想到dp f[u][i]表示到点u，且比到u的最短距离多i的方案数 那么需要先预处理dis数组，spfa或者堆优化的dijk 因为考虑到dp的顺序，f[u][i]转移到...DP,记忆化搜索,spfa
[BZOJ2118] 墨墨的等式（最短路）
[BZOJ4992] [Usaco2017 Feb]Why Did the Cow Cross the Road（spfa）
传送门 把每个点和曼哈顿距离距离它3步或1步的点连一条边，边权为3 * t + a[x][y] 因为，走3步，有可能是3步，也有可能是1步（其中一步拐了回来） 最后，把终点和曼哈顿距离距离它1步和2布...spfa,最短路
[BZOJ1663] [Usaco2006 Open]赶集（spfa最长路）
传送门 按照时间t排序 如果 t[i] + map[i][j] = t[j]，就在i和j之间连一条边 然后spfa找最长路 #include queue#include cstdio#include ...最短路,spfa
[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,最短路
[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,最短路
[luoguP3275] [SCOI2011]糖果（差分约束）
传送门 差分约束裸题 但是坑！ 有一个点是长为10W的链，需要逆序加边才能过（真是玄学） 还有各种坑爹数据 开longlong ——代码 1 #include cstdio 2 #include cs...spfa,差分约束,负环
[luoguP1993] 小 K 的农场（差分约束 + spfa 判断负环）
传送门 差分约束系统。。找负环用spfa就行 ——代码 1 #include cstdio 2 #include cstring 3 #include iostream 4 #define N 100...负环,spfa,差分约束
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化