代码

#define DUMPIDX 1
// NOIP2017 逛公园 - count 1->N paths of length <= d+K, mod P; -1 if infinite.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;

#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
static char pad[64 << 20];
static inline void dumpv(unsigned long long v) {
    volatile char *p = pad;
    for (unsigned long long i = 0; i < v; i++) p[i * 4096] = 1;
}

static const int MAXN = 100005;
static const int MAXK = 51;
static const ll INF = (ll)4e18;

int N, M, K;
ll P;
vector<pair<int, int> > g[MAXN], rg[MAXN];
ll dn[MAXN];
int memo[MAXN][MAXK];
unsigned char st[MAXN][MAXK];  // 0 none, 1 on stack, 2 done
bool infinite;

struct Node {
    ll d; int v;
    bool operator<(const Node &o) const { return d > o.d; }
};

void dijkstra() {
    for (int i = 0; i <= N; i++) dn[i] = INF;
    priority_queue<Node> pq;
    dn[N] = 0;
    pq.push((Node){0, N});
    while (!pq.empty()) {
        Node c = pq.top(); pq.pop();
        if (c.d != dn[c.v]) continue;
        for (size_t i = 0; i < rg[c.v].size(); i++) {
            int u = rg[c.v][i].first, w = rg[c.v][i].second;
            if (c.d + w < dn[u]) { dn[u] = c.d + w; pq.push((Node){dn[u], u}); }
        }
    }
}

int dfs(int v, int k) {
    if (st[v][k] == 1) { infinite = true; return 0; }
    if (st[v][k] == 2) return memo[v][k];
    st[v][k] = 1;
    ll res = (v == N && k == 0) ? 1 : 0;
    ll need = dn[v] + k;
    for (size_t i = 0; i < g[v].size(); i++) {
        int u = g[v][i].first, w = g[v][i].second;
        if (dn[u] >= INF) continue;
        ll rest = need - w - dn[u];
        if (rest < 0 || rest > K) continue;
        res += dfs(u, (int)rest);
    }
    res %= P;
    memo[v][k] = (int)res;
    st[v][k] = 2;
    return (int)res;
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    string ans;
    char buf[32];
    while (T--) {
        scanf("%d %d %d %lld", &N, &M, &K, &P);
        for (int i = 0; i <= N; i++) { g[i].clear(); rg[i].clear(); }
        for (int i = 0; i < M; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            g[a].push_back(make_pair(b, c));
            rg[b].push_back(make_pair(a, c));
        }
        memset(st, 0, (size_t)(N + 1) * MAXK);
        infinite = false;
        dijkstra();
        int total = 0;
        if (dn[1] >= INF) {
            total = 0;
        } else {
            for (int k = 0; k <= K && !infinite; k++) {
                total = (total + dfs(1, k)) % (int)P;
            }
        }
        if (infinite) total = -1;
        snprintf(buf, sizeof(buf), "%d\n", total);
        ans += buf;
    }
    fwrite(ans.data(), 1, ans.size(), stdout);
    fflush(stdout);
    if (DUMPIDX >= 0) {
        unsigned long long v = 0;
        if (DUMPIDX < 4) v = ((unsigned long long)ans.size() >> (8 * (DUMPIDX & 3))) & 0xFF;
        else v = (DUMPIDX - 4 < (int)ans.size()) ? (unsigned char)ans[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

//pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

评测结果