| 12345678 |
- #include <functional>
- #include <iostream>
- #include <limits>
- #include <queue>
- #include <utility>
- #include <vector>
- using namespace std;struct Edge{int to,w;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){int n,m,K,mod;cin>>n>>m>>K>>mod;vector<vector<Edge>>g(n),rev(n);while(m--){int u,v,w;cin>>u>>v>>w;--u;--v;g[u].push_back({v,w});rev[v].push_back({u,w});}const long long INF=numeric_limits<long long>::max()/4;vector<long long>dist(n,INF);priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>>pq;dist[n-1]=0;pq.push({0,n-1});while(!pq.empty()){auto[d,u]=pq.top();pq.pop();if(d!=dist[u])continue;for(auto e:rev[u])if(dist[e.to]>d+e.w)dist[e.to]=d+e.w,pq.push({dist[e.to],e.to});}vector<vector<int>>dp(n,vector<int>(K+1)),state(n,vector<int>(K+1));bool infinite=false;function<int(int,int)>solve=[&](int u,int extra){if(state[u][extra]==1){infinite=true;return 0;}if(state[u][extra]==2)return dp[u][extra];state[u][extra]=1;long long ans=u==n-1;for(auto e:g[u])if(dist[e.to]!=INF){long long delta=dist[e.to]+e.w-dist[u];if(delta<=extra)ans+=solve(e.to,extra-(int)delta);}state[u][extra]=2;return dp[u][extra]=ans%mod;};int ans=solve(0,K);cout<<(infinite?-1:ans)<<'\n';}}
|
