代码

// This code is AI-generated. (AI 生成的代码)
// NOIP2017 逛公园: Dijkstra from 1 and from n (flat CSR graphs), then a
// K-layer DP in shortest-path-DAG topological order.  A zero-extra cycle on a
// feasible path means infinitely many routes.
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;

enum { MAXN = 100005, MAXE = 400005, MAXK = 55 };
static int hd[MAXN], nx_[MAXE], to_[MAXE], wt_[MAXE], ec;
static int rh[MAXN], rnx[MAXE], rto[MAXE], rwt[MAXE], rec;
static ll d1[MAXN], dn[MAXN];
static char rel[MAXN];
static int indeg[MAXN], topo[MAXN], q[MAXN];
static unsigned dp[MAXK][MAXN];
static char buf[1 << 25];
static char ob[1 << 23];

static void ae(int u, int v, int w) {
    to_[ec] = v; wt_[ec] = w; nx_[ec] = hd[u]; hd[u] = ec++;
}
static void rae(int u, int v, int w) {
    rto[rec] = v; rwt[rec] = w; rnx[rec] = rh[u]; rh[u] = rec++;
}
static pli heap[MAXE];
static int hn;
static inline void hpush(pli x) {
    int i = hn++;
    heap[i] = x;
    while (i) {
        int p = (i - 1) >> 1;
        if (heap[p].first <= heap[i].first) break;
        pli tmp = heap[p]; heap[p] = heap[i]; heap[i] = tmp;
        i = p;
    }
}
static inline pli hpop() {
    pli r = heap[0];
    heap[0] = heap[--hn];
    int i = 0;
    for (;;) {
        int l = 2 * i + 1, rr = l + 1, m = i;
        if (l < hn && heap[l].first < heap[m].first) m = l;
        if (rr < hn && heap[rr].first < heap[m].first) m = rr;
        if (m == i) break;
        pli tmp = heap[m]; heap[m] = heap[i]; heap[i] = tmp;
        i = m;
    }
    return r;
}
static void dij(int n, int *h, int *t, int *w, int *nx, int s, ll *d) {
    const ll INF = (ll)4e18;
    for (int i = 1; i <= n; i++) d[i] = INF;
    hn = 0;
    d[s] = 0; hpush(pli(0, s));
    while (hn) {
        pli x = hpop();
        int u = x.second;
        if (x.first != d[u]) continue;
        for (int e = h[u]; e; e = nx[e]) {
            ll nd = x.first + w[e];
            int v = t[e];
            if (nd < d[v]) { d[v] = nd; hpush(pli(nd, v)); }
        }
    }
}
static const char *gp;
static inline ll nx() {
    while (*gp && (*gp < '0' || *gp > '9')) gp++;
    ll v = 0;
    while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0');
    return v;
}
static char *op;
static inline void pn(ll v) {
    char t[24]; int k = 0;
    if (v < 0) { *op++ = '-'; v = -v; }
    if (!v) t[k++] = '0';
    while (v) { t[k++] = (char)('0' + v % 10); v /= 10; }
    while (k) *op++ = t[--k];
    *op++ = '\n';
}

int main() {
    int len = (int)fread(buf, 1, sizeof(buf) - 1, stdin);
    buf[len] = 0;
    gp = buf; op = ob;
    const ll INF = (ll)4e18;
    int T = (int)nx();
    while (T--) {
        int n = (int)nx(), m = (int)nx(), K = (int)nx();
        ll mod = nx();
        ec = 1; rec = 1;
        for (int i = 0; i <= n; i++) { hd[i] = 0; rh[i] = 0; }
        for (int i = 0; i < m; i++) {
            int u = (int)nx(), v = (int)nx(), w = (int)nx();
            ae(u, v, w); rae(v, u, w);
        }
        dij(n, hd, to_, wt_, nx_, 1, d1);
        dij(n, rh, rto, rwt, rnx, n, dn);
        if (d1[n] >= INF) { pn(0); continue; }
        ll bound = d1[n] + K;
        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++; }
            else rel[i] = 0;
            indeg[i] = 0;
        }
        for (int u = 1; u <= n; u++) {
            if (!rel[u]) continue;
            for (int e = hd[u]; e; e = nx_[e]) {
                int v = to_[e];
                if (rel[v] && d1[u] + wt_[e] == d1[v]) indeg[v]++;
            }
        }
        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++];
            for (int e = hd[u]; e; e = nx_[e]) {
                int v = to_[e];
                if (rel[v] && d1[u] + wt_[e] == d1[v] && --indeg[v] == 0) q[tl++] = v;
            }
        }
        if (tl < relcnt) { pn(-1); continue; }
        for (int i = 0; i < tl; i++) topo[i] = q[i];
        for (int j = 0; j <= K; j++)
            for (int i = 0; i <= n; i++) dp[j][i] = 0;
        dp[0][1] = (unsigned)(1 % mod);
        for (int j = 0; j <= K; j++) {
            for (int idx = 0; idx < tl; idx++) {
                int u = topo[idx];
                unsigned val = dp[j][u];
                if (!val) continue;
                for (int e = hd[u]; e; e = nx_[e]) {
                    int v = to_[e];
                    if (!rel[v]) continue;
                    ll delta = d1[u] + wt_[e] - d1[v];
                    if (delta < 0 || j + delta > K) continue;
                    unsigned *x = &dp[j + delta][v];
                    unsigned s = *x + val;
                    if (s >= (unsigned)mod) s -= (unsigned)mod;
                    *x = s;
                }
            }
        }
        unsigned ans = 0;
        for (int j = 0; j <= K; j++) {
            ans += dp[j][n];
            if (ans >= (unsigned)mod) ans -= (unsigned)mod;
        }
        pn(ans);
    }
    fwrite(ob, 1, op - ob, stdout);
    return 0;
}

评测结果