「NOIP 2017」逛公园

乱七八糟

我好弱啊

这一题只想到递推 DP

又没有想出正解

到现在还是这么菜

NOIP 2019 如何 500+

首先发现 $k$ 很小，自然地想到 DP

令 $d$ 表示最短路

$f_{u, x}$ 代表从 $s$ 到 $u$ 路径长为 $d_u + x$ 的方案数量

如何转移？

用记忆化搜索比较自然，而且也容易判 $0$ 环（DFS 的性质比较好）

假设当前在求 $f_{u, x}$，$v$ 为有 $v\rightarrow u$ 边的点，$w$ 为边权

$$f_{u,x} = \sum f_{v, x+d_u-w-d_v}$$

环判定就

woc 这题我 Dijkstra 还写挂了

具体看代码

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

const int BUF = 50000000;
struct IOStream {
    char ibuf[BUF], *s;
    char obuf[BUF], *oh;
    IOStream() : s(ibuf), oh(obuf) { ibuf[fread(ibuf, 1, BUF, stdin)] = '\0'; }
    ~IOStream() { fwrite(obuf, 1, oh - obuf, stdout); }
    template <typename T>
    inline IOStream &operator>>(T &x) {
        while (!isdigit(*s)) s++;
        for (x = 0; isdigit(*s); s++) x = x * 10 + (*s ^ '0');
        return *this;
    }
} cin;
using std::cout;

const int N = 100010;
const int M = 200010;
int P, n, m, k;
struct Graph {
    struct Edge {
        int v, w;
        Edge *nxt;
    } e[M];
    int cnt = 0;
    Edge *p[N];
    void clear() {
        std::memset(p, 0, sizeof(p));
        cnt = 0;
    }
    void addedge(int u, int v, int w) {
        e[cnt].v = v, e[cnt].w = w, e[cnt].nxt = p[u], p[u] = &e[cnt++];
    }
} g, fg;

int dis[N], flg[N];
std::priority_queue<pii, std::vector<pii>, std::greater<pii> > q;
void dijkstra(int s) {
    std::memset(dis, -1, sizeof(dis));
    std::memset(flg, 0, sizeof(flg));
    dis[s] = 0;
    q.push({0, s});
    while (q.size()) {
        pii cur = q.top();
        q.pop();
        if (flg[cur.second]) continue;
        flg[cur.second] = 1;
        for (Graph::Edge *i = g.p[cur.second]; i != nullptr; i = i->nxt) {
            if (!flg[i->v] &&
                (dis[i->v] == -1 || dis[i->v] > cur.first + i->w)) {
                dis[i->v] = cur.first + i->w;
                q.push({dis[i->v], i->v});
            }
        }
    }
}

int f[N][52], vis[N][52];
int now = 0;
bool zp = 0; // 环判定
int work(int u, int lk) {
    if (zp) return 0;
    if (f[u][lk] != -1) return f[u][lk];
    vis[u][lk] = 1;
    f[u][lk] = 0;
    for (Graph::Edge *i = fg.p[u]; i != NULL && !zp; i = i->nxt) {
        int nk = lk + dis[u] - i->w - dis[i->v];
        if (nk > k || nk < 0 || dis[i->v] == -1) continue;
        if (vis[i->v][nk]) {
            zp = 1;
            return 0;
        }
        f[u][lk] = (f[u][lk] + work(i->v, nk)) % P;
    }
    vis[u][lk] = 0;
    return f[u][lk];
}

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    int T;
    cin >> T;
    while (T--) {
        g.clear(), fg.clear();
        std::memset(f, -1, sizeof(f));
        std::memset(vis, 0, sizeof(vis));
        zp = 0;
        int t_t = clock();
        cin >> n >> m >> k >> P;
        rep(i, 1, m) {
            int u, v, w;
            cin >> u >> v >> w;
            g.addedge(u, v, w), fg.addedge(v, u, w);
        }
        g.addedge(0, 1, 0), fg.addedge(1, 0, 0);
        dijkstra(0);
        // 特别的，这里采取加入虚点 0 来防止环由 1 号点构成而判不出来
        // 就是你样例过不去的意思 233
        cerr << "dij " << ((double)clock() - t_t) / CLOCKS_PER_SEC << endl;
        t_t = clock();
        int ans = 0;
        f[0][0] = 1;
        rep(i, 0, k) {
            now = i;
            ans = (ans + work(n, i)) % P;
        }
        if (zp)
            printf("-1\n");
        else
            printf("%d\n", ans);
        cerr << "work " << ((double)clock() - t_t) / CLOCKS_PER_SEC << endl;
    }

    return 0;
}