[BZOJ4992] [Usaco2017 Feb]Why Did the Cow Cross the Road（spfa）

传送门

把每个点和曼哈顿距离距离它3步或1步的点连一条边，边权为3 * t + a[x][y]

因为，走3步，有可能是3步，也有可能是1步（其中一步拐了回来）

最后，把终点和曼哈顿距离距离它1步和2布的点连一条边，边权为 步数 * t

跑一边spfa即可

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#define N 1000001#define idx(i, j) ((i  1) * n + j)using namespace std;int n, t, cnt;int a[101][101], d[4][N][2], tot[4];int head[N], to[N], next[N], val[N], dis[N];bool vis[N];queue <int> q;inline int read()inline void add(int x, int y, int z)inline void spfa()}}}}int main()memset(head, 1, sizeof(head));for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)a[i][j] = read();for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)for(l = 1; l <= 3; l += 2)for(k = 1; k <= tot[l]; k++)for(i = 1; i <= 2; i++)for(j = 1; j <= tot[i]; j++)spfa();printf("%d\n", dis[n * n]);return 0;}

上一篇：[BZOJ1594] [Usaco2008 Jan]猜数游戏（二分 + 并查集）

下一篇：[BZOJ1595] [Usaco2008 Jan]人工湖（单调栈）