[NOIP2017 提高组] 逛公园 （题解）
Step 1(30pts).
最短路计数，可以参考 [NOI2007] 社交网络。
Step 2(70pts)
考虑图中没有
0
0
0 边的情况，此时是必然有解的。用
d
(
u
)
d(u)
d(u) 表示从
1
1
1 到
u
u
u 的最短路径长度，那么要求的答案就是从
1
1
1 到
n
n
n 的长度不超过
d
(
n
)
+
K
d(n)+K
d(n)+K 的路径。这个问题可以用 DP 求解，设
f
(
u
;
k
)
f(u;k)
f(u;k) 表示从
1
1
1 到
u
u
u 的长度为
d
(
u
)
+
k
d(u)+k
d(u)+k 的路径数，则转移如下
f
(
u
;
k
)
=
∑
(
v
,
u
,
w
)
∈
E
f
(
v
;
k
−
w
+
(
d
(
u
)
−
d
(
v
)
)
)
f(u;k) = \sum_{(v,u,w)\in E} f(v;k-w+(d(u)-d(v)))
f(u;k)=(v,u,w)∈E∑f(v;k−w+(d(u)−d(v)))
至于按照什么顺序转移，无需考虑太多，直接记忆化搜索即可
int dfs(int u, int k) {
if (k < 0) return 0;
if (f[u][k] != 0) return f[u][k];
int ret = 0;
// G1 是反向图
for (auto it = G1[u].begin(); it != G1[u].end(); ++it) {
int v = it->v, w = it->w;
ret = (ret + dfs(v, d[u] - d[v] + k - w)) % P;
}
return f[u][k] = ret;
}
Step 3(100pts).
现在考虑如何处理有 0 0 0 边的情况，如果直接从图上考虑是否存在 0 0 0 环，将产生十分复杂的讨论（因为有 0 0 0 环不一定会造成无穷多的解）。更合理的一种方式是直接在记忆化搜索时记录当前的搜索路径，由于 DP 的正确性的前提是所有的状态能构成一个 DAG，而如果记忆话搜索的路径出现了环，就说明有无穷多个解
int dfs(int u, int k) {
if (k < 0) return 0;
if (inPath[u][k]){
flag = true; // flag 判断是否有无穷多个解
return 0;
}
if (f[u][k] != 0) return f[u][k];
inPath[u][k] = true;
int ret = 0;
// G1 是反向图
for (auto it = G1[u].begin(); it != G1[u].end(); ++it) {
int v = it->v, w = it->w;
ret = (ret + dfs(v, d[u] - d[v] + k - w)) % P;
if (flag) return 0;
}
inPath[u][k] = false;
return f[u][k] = ret;
}