【思路点拨】 是个人应该都能看出此题是要先求出最短路.jpg 亲测此题SPFA跑的比Dijkstra快 为什么?我人品好 最短路只能求出路径长度,计算路径条数似乎做不到—— 然后就gg了 据说NOIP2017 Day1三题都没有DP 作为Day2压轴题 DP是压轴出场 What is DP? Is that Dui Pai?
inlinevoidadd(ll &a, ll b){ //究极玄学卡常 a += b; if (a > p) { a -= p; } }
inlinevoidSPFA(){ vis[1] = 1; dis[1] = 0; queue<ll> q; q.push(1); while (!q.empty()) { ll x = q.front(); q.pop(); for (ri i = head[x]; i != 0; i = pre[i]) { ll y = to[i]; if (dis[y] > dis[x] + val[i]) { dis[y] = dis[x] + val[i]; if (!vis[y]) { vis[y] = 1; q.push(y); } } } vis[x] = 0; } }
ll dfs(ll c, ll nowk){ if (dp[c][nowk] != -1) return dp[c][nowk]; visit[c][nowk] = 1; dp[c][nowk] = 0; for (ri i = head2[c]; i; i = pre2[i]) { ll next = dis[c] - dis[to2[i]] + nowk - val2[i]; if (next < 0) continue; if (visit[to2[i]][next]) { ok = 1; } add(dp[c][nowk], dfs(to2[i], next)); } visit[c][nowk] = 0; return dp[c][nowk]; }
voidThis_is_a_dp(){ dp[1][0] = 1; for (ri i = 0; i <= k; i++) { add(ans, dfs(n, i)); } }
intmain(){ t = read(); while (t--) { memset(head, 0, sizeof(head)); memset(head2, 0, sizeof(head2)); memset(dp, -1, sizeof(dp)); memset(visit, 0, sizeof(visit)); memset(vis, 0, sizeof(vis)); memset(dis, 0x7f, sizeof(dis)); ok = 0; len = ans = len2 = 0; n = read(); m = read(); k = read(); p = read(); for (ri i = 1; i <= m; i++) { ll u, v, w; u = read(); v = read(); w = read(); insert(u, v, w); insert2(v, u, w); } SPFA(); /*DP!*/ This_is_a_dp(); dfs(n, k + 1); if (ok) { puts("-1"); continue; } write(ans); puts(""); } return0; }