「NOIP2017」逛公园

传送门

Luogu

解题思路

考虑 \(\text{DP}\)。

设 \(f[u][k]\) 表示从 \(u\) 到 \(n\) 走过不超过 \(Mindis(u, n) + k\) 距离的方案数。

转移方程为:\(f[u][k] = \sum{f[v][k + Mindis(u,n) - Mindis(v,n) - dis(u,v)]}\)

\(Mindis\) 可以预处理。

无解的情况直接在记搜的时候把 \(-1\) 传上去。

最后输出 \(f[1][k]\) 即可。

细节注意事项

  • 要记得有多组数据,每次都要初始化

参考代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= (c == '-'), c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
const int _ = 100010;
const int __ = 400010;
int n, m, kk, p;
int tot, head1[_], headn[_], nxt[__], ver[__], w[__];
inline void Add_edge(int u, int v, int d, int* head)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, w[tot] = d; }
struct node{ int val, u; };
inline bool operator < (const node& x, const node& y) { return x.val > y.val; }
int dis[_], vis[_];
priority_queue < node > q;
inline void dijkstra() {
memset(vis, 0, sizeof vis);
memset(dis, 0x3f, sizeof dis);
dis[n] = 0, q.push((node) { 0, n });
while (!q.empty()) {
int u = q.top().u; q.pop();
if (vis[u]) continue; vis[u] = 1;
for (rg int i = headn[u]; i; i = nxt[i]) {
int v = ver[i];
if (dis[v] > dis[u] + w[i])
dis[v] = dis[u] + w[i], q.push((node) { dis[v], v });
}
}
}
int st[_][55], f[_][55];
inline int dfs(int u, int k) {
if (st[u][k]) return -1;
if (f[u][k]) return f[u][k];
st[u][k] = 1;
if (u == n) f[u][k] = 1;
for (rg int i = head1[u]; i; i = nxt[i]) {
int v = ver[i], tmp = dis[v] + w[i] - dis[u];
if (tmp <= k) {
int res = dfs(v, k - tmp);
if (res != -1) f[u][k] = (f[u][k] + res) % p;
else return f[u][k] = -1;
}
}
return st[u][k] = 0, f[u][k];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
int T; read(T);
while (T--) {
read(n), read(m), read(kk), read(p);
tot = 0;
memset(head1, 0, sizeof head1);
memset(headn, 0, sizeof headn);
for (rg int u, v, d, i = 1; i <= m; ++i)
read(u), read(v), read(d), Add_edge(u, v, d, head1), Add_edge(v, u, d, headn);
dijkstra();
memset(f, 0, sizeof f);
memset(st, 0, sizeof st);
printf("%d\n", dfs(1, kk));
}
return 0;
}

完结撒花 \(qwq\)

上一篇:NOIP2017:逛公园


下一篇:【NOIP2017】逛公园 最短路+DP