题解 | #草药大师#

调试的一晚上，终于AC了哈哈

其实就是 最短路+记忆化搜索

但是思考这道题的解法的时候想了很长时间，主要是因为 判零环逻辑 和 dp遍历方式 没搞好（想得十分复杂），最短路那一块反而没那么难

可以用vis数组标记当前处于遍历状态遍历的结点，如果遍历到合法的标记vis的状态，那么就说明存在零环，直接-1退出即可

这里非常想感慨一下，记忆化搜索真的很好用，尤其是在这种状态转移顺序与图的遍历密切相关的地方

最后放一下代码：

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << #x << ": " << x << endl 
int n , m , k , p ;
const int maxN = 1e5+10 , maxM = 2e5+10, maxK = 51 ;

vector<array<int,2>> g[maxN] , rg[maxN] ;


bool dijkstra(int n,int s, int t, vector<int> &dist) {
    vector<unsigned char> vis(n+1,false) ;
    dist[s] = 0 ;
    priority_queue<array<int,2>, vector<array<int,2>>, greater<array<int,2>>> que ;
    que.push({0,s}) ;
    while(!que.empty()) {
        int u = que.top()[1] ;    que.pop() ;
        if(vis[u])    continue ;
        vis[u] = true ;
        for(auto &[v,w]:g[u]) {
            if(dist[v]>dist[u]+w) {
                dist[v] = dist[u] + w ;
                que.push({dist[v],v}) ;
            }
        }
    }
    return vis[t] ;
}

int dfs(int u, int j, vector<vector<int>> &dp, vector<int> &dist, vector<vector<unsigned char>> &vis) {
    if(dp[u][j]!=-1)    return dp[u][j] ;
    vis[u][j] = true ;
    int res = 0 ;
    for(auto &[v,w]:rg[u]) {
        int vj = dist[u]+j-w-dist[v] ;
        if(vj<0 || vj>k)    continue ;
        if(vis[v][vj]) 
            return -1 ;
        int add = dfs(v,vj,dp,dist,vis) ;
        if(add == -1)
            return -1 ;
        res = (res + add)%p ;
    }
    vis[u][j] = false ;
    return dp[u][j] = res+(u==1) ;
}

void solve() {
    cin >> n >> m >> k >> p ;
    for(int i=1 ; i<=n ; i++) {
        g[i].clear() , rg[i].clear() ;
    }
    for(int i=1 ; i<=m ; i++) {
        int u , v , w ;    cin >> u >> v >> w ;
        g[u].push_back({v,w}) ;
        rg[v].push_back({u,w}) ;
    }

    vector<int> dist(n+1,inf) ;
    if(!dijkstra(n,1,n,dist)) {
        cout << 0 << endl ;
        return ;
    }
    
    vector<vector<int>> dp(n+1, vector<int>(k+1,-1)) ;
    vector<vector<unsigned char>> vis(n+1,vector<unsigned char>(k+1,false)) ;
    int res = dfs(n,k,dp,dist,vis) ;
    if(res == -1) {
        cout << -1 << endl ;
        return ;
    }
        
    cout << res << endl ;
}

signed main() {
    int t ;    cin >>t ;
    while(t--)    solve() ;
    return 0 ;
}