[luoguP3953] 逛公园（DP + spfa）

传送门

看到求方案数，应该很容易想到dp

f[u][i]表示到点u，且比到u的最短距离多i的方案数

那么需要先预处理dis数组，spfa或者堆优化的dijk

因为考虑到dp的顺序，f[u][i]转移到f[v][j]时，j不可能小于i

所以需要从0到k枚举i，然后从最后一个点开始记忆化搜索

至于判断0环，只需要在记忆化搜索的时候加一个栈即可

1A的代码，哈哈

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#define N 200001using namespace std;int T, n, m, k, p, cnt, cnt1, ans;int head[N], to[N], nex[N], val[N], head1[N], to1[N], nex1[N], val1[N], f[N][51], dis[N];bool flag, vis[N], vis1[N][51], ins[N][51];queue <int> q;inline int read()inline void add(int x, int y, int z)inline void add1(int x, int y, int z)inline void spfa()}}}}inline void init()spfa();f[1][0] = 1;}inline void clear()inline int dfs(int u, int i)vis1[u][i] = 1;ins[u][i] = 0;return f[u][i];}inline int solve()return ans;}int main()return 0;}

上一篇：[luoguP2495] [SDOI2011]消耗战（DP + 虚树）

下一篇：[luoguP1963] [NOI2009]变换序列（二分图最大匹配）