题意

题目链接

Sol

去年考NOIP的时候我好像连最短路计数都不会啊qwq。。

首先不难想到一个思路，\(f[i][j]\)表示到第\(i\)个节点，与最短路之差长度为\(j\)的路径的方案数

首先把每个节点的最短路求出来

转移的时候按拓扑序(也就是按距离从小到大排序)转移一下

然而有\(0\)边的时候会挂掉，原因是会有dis相同的时候，这时候单按dis排序会无法判断转移方向

一种方案是直接把所有\(0\)边加入到新图中，拓扑排序一遍。得到第二关键字

同时判断一下\(0\)环

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define MP make_pair

#define fi first

#define se second

using namespace std;

const int MAXN = 100001, INF = 1e9 + 7;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int T, N, M, K, mod, f[MAXN][51], dis1[MAXN], disn[MAXN], vis[MAXN], inder[MAXN], id[MAXN];

vector<Pair> v[MAXN], rv[MAXN];

vector<pair<pair<int, int>, int> > P;

vector<int> E[MAXN];

void init() {

    memset(f, 0, sizeof(f));

    memset(inder, 0, sizeof(inder));

    P.clear();

    f[1][0] = 1;

    N = read(); M = read(); K = read(); mod = read();

    for(int i = 1; i <= N; i++) v[i].clear(), E[i].clear();

    for(int i = 1; i <= M; i++) {

        int x = read(), y = read(), z = read();

        v[x].push_back(MP(y, z)); rv[y].push_back(MP(x, z));

        if(!z) E[x].push_back(y), inder[y]++;

    }

}

void add(int &x, int y) {

    if(x + y < 0) x = (x + y + mod);

    else x = (x + y >= mod ? x + y - mod : x + y);

}

int Topsort() {

    int cnt = 0; queue<int> q;

    for(int i = 1; i <= N; i++) if(!inder[i]) id[i] = ++cnt, q.push(i);

    while(!q.empty()) {

        int p = q.front(); q.pop();

        for(int i = 0, to; i < E[p].size(); i++)

            if(!(--inder[to = E[p][i]])) q.push(to), id[to] = ++cnt;

    }

    for(int i = 1; i <= N; i++) if(inder[i] && (dis1[i] + disn[i] <= dis1[N] + K)) return -1;

    return 0;

}

void Dij(int bg, int *dis) {

    priority_queue<Pair> q; q.push(MP(0, bg));

    memset(vis, 0, sizeof(vis));

    for(int i = 1; i <= N; i++) dis[i] = INF + 1; dis[bg] = 0;

    while(!q.empty()) {

        if(vis[q.top().se]) {q.pop(); continue;}

        int p = q.top().se; q.pop(); vis[p] = 1;

        if(bg == 1) {

            for(int i = 0, to; i < v[p].size(); i++)

                if(dis[to = v[p][i].fi] > dis[p] + v[p][i].se)

                    dis[to] = dis[p] + v[p][i].se, q.push(MP(-dis[to], to));

        } else {

            for(int i = 0, to; i < rv[p].size(); i++)

                if(dis[to = rv[p][i].fi] > dis[p] + rv[p][i].se)

                    dis[to] = dis[p] + rv[p][i].se, q.push(MP(-dis[to], to));

        }

    }

}

int solve() {

    Dij(1, dis1);

    Dij(N, disn);

    if(Topsort() == -1) return -1;

    for(int i = 1; i <= N; i++) P.push_back(MP(MP(dis1[i], id[i]), i));

    sort(P.begin(), P.end());

    f[1][0] = 1;

    for(int j = 0; j <= K; j++) {

        for(int i = 0; i < N; i++) {

            int x = P[i].se;

            for(int k = 0; k < v[x].size(); k++) {

                int to = v[x][k].fi, w = v[x][k].se, ps = dis1[x] + j + w - dis1[to];

                if(ps <= K) add(f[to][ps], f[x][j]);

            }

        }

    }

    int ans = 0;

    for(int i = 0; i <= K; i++) add(ans, f[N][i]);

    return ans;

}

int main() {

    T = read();

    while(T--) {

        init();

        printf("%d\n", solve());

    }

    return 0;

}

/*

*/