Luogu

LOJ

分析

考虑 DP。设 $dp_{u,k}$ 表示 $u\to n$ 的比最短路长至多 $k$ 的路径条数。

转移时我们需要知道走 $(u,v,w)$ 这条边后路径长度会比最短路长多少。建反图跑 dijkstra 求出每个点到 $n$ 的最短路，然后就很容易得到这个东西了。

显然存在一个可以到达的 $0$ 环则无解。在记搜的时候如果搜到了自己就说明有可以到达的 $0$ 环，输出 -1 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,K=50+10;
int mod;

int n,m,k;
vector<pair<int,int> > E[N],fE[N];

struct node { int u,d; };
bool operator <(node a,node b) { return a.d>b.d; }
int dis[N];
inline void dijkstra() {
    memset(dis,0x3f,sizeof(dis)),dis[n]=0;
    priority_queue<node> Q; Q.push((node){n,0});
    while (!Q.empty()) {
        int u=Q.top().u,d=Q.top().d; Q.pop();
        if (d!=dis[u]) continue;
        for (re auto nxt:fE[u]) {
            int v=nxt.first,w=nxt.second;
            if (dis[u]+w<dis[v])
                dis[v]=dis[u]+w,Q.push((node){v,dis[v]});
        }
    }
}

int vis[N][K],dp[N][K];
inline int dfs(int u,int k) {
    if (vis[u][k]) return -1;
    if (dp[u][k]) return dp[u][k];
    vis[u][k]=1,dp[u][k]=u==n?1:0;
    for (re auto nxt:E[u]) {
        int v=nxt.first,w=nxt.second,dlt=w-dis[u]+dis[v];
        if (dlt<=k) { int tmp=dfs(v,k-dlt);
            if (tmp==-1) { vis[u][k]=0; return dp[u][k]=-1; }
            else dp[u][k]=(dp[u][k]+tmp)%mod;
        }
    }
    vis[u][k]=0; return dp[u][k];
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read(),k=read(),mod=read();
        for (re int i=1;i<=m;++i) {
            int u=read(),v=read(),w=read();
            E[u].push_back(make_pair(v,w));
            fE[v].push_back(make_pair(u,w));
        }
        dijkstra(); printf("%d\n",dfs(1,k));
        for (re int i=1;i<=n;++i) E[i].clear(),fE[i].clear();
        memset(dp,0,sizeof(dp));
    }
    return 0;
}