「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\)