代码

// This code is AI-generated. (AI 生成的代码)
// NOIP2017 逛公园: Dijkstra from 1 and from n; then DP over (node, extra<=K).
// A zero-extra cycle reachable on a feasible path means infinitely many routes.
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;

struct DuckInfo {
    unsigned long long abi;
    const char *in; unsigned long long in_size;
    char *out; unsigned long long out_limit; unsigned long long out_size;
    char *err; unsigned long long err_limit; unsigned long long err_size;
    const char *ib; unsigned long long ib_limit;
    char *ob; unsigned long long ob_limit; unsigned long long tsc;
} __attribute__((packed));

static const char *g_p;
static inline ll nx() {
    while (*g_p && (*g_p < '0' || *g_p > '9')) g_p++;
    ll v = 0;
    while (*g_p >= '0' && *g_p <= '9') v = v * 10 + (*g_p++ - '0');
    return v;
}
static char *g_o;
static inline void putnum(ll v) {
    char t[24]; int k = 0;
    if (v < 0) { *g_o++ = '-'; v = -v; }
    if (!v) t[k++] = '0';
    while (v) { t[k++] = (char)('0' + v % 10); v /= 10; }
    while (k) *g_o++ = t[--k];
    *g_o++ = '\n';
}
static void dij(int n, vector<vector<pair<int,int>>> &g, int s, vector<ll> &d) {
    const ll INF = (ll)4e18;
    d.assign(n + 1, INF);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    d[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        pli t = pq.top(); pq.pop();
        if (t.first != d[t.second]) continue;
        int u = t.second;
        for (auto &e : g[u]) {
            ll nd = t.first + e.second;
            if (nd < d[e.first]) { d[e.first] = nd; pq.push({nd, e.first}); }
        }
    }
}

int main() {
    static char buf[1 << 25];
    int len = (int)fread(buf, 1, sizeof(buf) - 1, stdin);
    buf[len] = 0;
    g_p = buf;
    static char ob[1 << 22];
    g_o = ob;

    
    
    int T = (int)nx();
    const ll INF = (ll)4e18;
    while (T--) {
        int n = (int)nx(), m = (int)nx(), K = (int)nx();
        ll mod = nx();
        vector<vector<pair<int,int>>> g(n + 1), rg(n + 1);
        for (int i = 0; i < m; i++) {
            int u = (int)nx(), v = (int)nx(), w = (int)nx();
            g[u].push_back({v, w});
            rg[v].push_back({u, w});
        }
        vector<ll> d1, dn;
        dij(n, g, 1, d1);
        dij(n, rg, n, dn);
        if (d1[n] >= INF) { putnum(0); continue; }
        ll bound = d1[n] + K;
        vector<char> rel(n + 1, 0);
        int relcnt = 0;
        for (int i = 1; i <= n; i++)
            if (d1[i] < INF && dn[i] < INF && d1[i] + dn[i] <= bound) { rel[i] = 1; relcnt++; }
        /* Kahn topological order on delta==0 (shortest-path DAG) edges */
        vector<int> indeg(n + 1, 0);
        vector<vector<int>> dag(n + 1);
        for (int u = 1; u <= n; u++) {
            if (!rel[u]) continue;
            for (auto &ed : g[u]) {
                int v = ed.first;
                if (rel[v] && d1[u] + ed.second == d1[v]) { dag[u].push_back(v); indeg[v]++; }
            }
        }
        vector<int> topo; topo.reserve(relcnt);
        {
            static int q[100005];
            int h = 0, tl = 0;
            for (int i = 1; i <= n; i++) if (rel[i] && !indeg[i]) q[tl++] = i;
            while (h < tl) {
                int u = q[h++]; topo.push_back(u);
                for (int v : dag[u]) if (--indeg[v] == 0) q[tl++] = v;
            }
        }
        if ((int)topo.size() < relcnt) { putnum(-1); continue; }
        vector<vector<ll>> dp(n + 1, vector<ll>(K + 1, 0));
        dp[1][0] = 1 % mod;
        for (int j = 0; j <= K; j++) {
            for (int idx = 0; idx < (int)topo.size(); idx++) {
                int u = topo[idx];
                ll val = dp[u][j];
                if (!val) continue;
                for (auto &ed : g[u]) {
                    int v = ed.first;
                    if (!rel[v]) continue;
                    ll delta = d1[u] + ed.second - d1[v];
                    if (delta < 0 || j + delta > K) continue;
                    ll &x = dp[v][j + delta];
                    x = (x + val) % mod;
                }
            }
        }
        ll ans = 0;
        for (int j = 0; j <= K; j++) ans = (ans + dp[n][j]) % mod;
        putnum(ans);
    }
    fwrite(ob, 1, g_o - ob, stdout);
    return 0;
}

评测结果