Step 1(30pts).

最短路计数，可以参考 [NOI2007] 社交网络。

Step 2(70pts)

考虑图中没有 $0$ 边的情况，此时是必然有解的。用 $d(u)$ 表示从 $1$ 到 $u$ 的最短路径长度，那么要求的答案就是从 $1$ 到 $n$ 的长度不超过 $d(n)+K$ 的路径。这个问题可以用 DP 求解，设 $f(u;k)$ 表示从 $1$ 到 $u$ 的长度为 $d(u)+k$ 的路径数，则转移如下
f(u;k)=∑(v,u,w)∈Ef(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$ 环不一定会造成无穷多的解）。更合理的一种方式是直接在记忆化搜索时记录当前的搜索路径，由于 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;
}

推币机