【题解】LuoGu3953：逛公园

原题传送门 $NOIp2017tgD1T3$ 当然是先跑个$dijkstra$把最短路求出来 然后想到dp求答案 $d{p}_{u,d}$表示到$u$路程为$d$方案数 状态太多，看到$K<=50$ 更改状态$d{p}_{u,d}$表示路程为$di{s}_u+d$的方案数($di{s}_u$表示到$u$的最短路) 然后用加法原理转移

需要从最终态$n$跑到最初态$1$所以跑反图 直接拓扑上跑好像很麻烦，用记忆化$dfs$ 考虑一下-1的情况，就是0环的情况，开一个$fla{g}_{u,d}$的数组，如果重复到这个状态两遍就说明有0环

Code：

#include <bits/stdc++.h> #define maxn 200010 #define maxm 51 using namespace std; struct node{ int val, dis; bool operator < (const node &x) const{ return x.dis < dis; } }; priority_queue <node> q; struct Edge{ int to, next, len; }edge[maxn << 1], edge2[maxn << 1]; int num, num2, head[maxn], head2[maxn], dis[maxn], vis[maxn], flag[maxn][maxm], dp[maxn][maxm], n, m, K, P; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } void addedge(int x, int y, int z){ edge[++num] = (Edge){y, head[x], z}, head[x] = num; } void addedge2(int x, int y, int z){ edge2[++num2] = (Edge){y, head2[x], z}, head2[x] = num2; } void dijkstra(){ memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; ++i) dis[i] = 1e9; dis[1] = 0; q.push((node){1, 0}); while (!q.empty()){ node tmp = q.top(); q.pop(); int u = tmp.val, l = tmp.dis; if (vis[u]) continue; vis[u] = 1; for (int i = head[u]; i; i = edge[i].next){ int v = edge[i].to; if (dis[v] > dis[u] + edge[i].len){ dis[v] = dis[u] + edge[i].len; if (!vis[v]) q.push((node){v, dis[v]}); } } } } int dfs(int u, int l){ if (l < 0 || l > K) return 0; if (flag[u][l]) return -1; if (dp[u][l] != -1) return dp[u][l]; flag[u][l] = 1; int sum = 0; for (int i = head2[u]; i; i = edge2[i].next){ int v = edge2[i].to; int tmp = dfs(v, dis[u] + l - dis[v] - edge2[i].len); if (tmp == -1) return -1; (sum += tmp) %= P; } if (u == 1 && !l) ++sum; dp[u][l] = sum; flag[u][l] = 0; return sum; } int main(){ int Q = read(); while (Q--){ num = num2 = 0; memset(head, 0, sizeof(head)); memset(head2, 0, sizeof(head2)); n = read(), m = read(), K = read(), P = read(); for (int i = 1; i <= m; ++i){ int x = read(), y = read(), z = read(); addedge(x, y, z); addedge2(y, x, z); } dijkstra(); memset(dp, 255, sizeof(dp)); memset(flag, 0, sizeof(flag)); int ans = 0, flag = 0; for (int i = 0; i <= K; ++i){ int tmp = dfs(n, i); if (tmp == -1){ flag = 1; break; } (ans += tmp) %= P; } if (!flag) printf("%lld\n", ans); else puts("-1"); } return 0; }