[NOIP2017]逛公园

考虑dp，dp[i][j]表示到 i 个点，最短路比当前长 j 的方案数，因为正向dp转移考虑比较困难，考虑记忆化搜索，当前点的贡献等于后继所有节点的贡献相加。

		int res=d[x]-d[u]+c-w;if(res<0) continue;if(vis[u][res]) ok=1;dp[x][c]+=f(u,res);

最后注意存在0环的情况，即这种情况方案数无限多，那么什么时候会出现这种情况，当我们进行dfs时，对于一个相同的状态在标记之后再遇见一次，那么此时就代表遇见了零环

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const int maxv = 4e6 + 5;
typedef pair<ll, ll> pll;
typedef array<ll,3> ar;
// #define endl "\n"
// typedef pair<double,pair<int,int> > pb;int n,m,k,p;vector<pll> e[N],e1[N];void add(int u,int v,int w)
{e[u].push_back({v,w});e1[v].push_back({u,w});
}
bool st[N];
int d[N];void dijk(int s)
{priority_queue<pll,vector<pll>,greater<pll> > q;q.push({0,s});memset(d,0x3f,sizeof d);memset(st,0,sizeof st);d[s]=0;while(!q.empty()){auto [dis,u]=q.top();q.pop();if(st[u]) continue;st[u]=1;for(auto [v,w] :e[u]){if(d[v]>d[u]+w){d[v]=d[u]+w;q.push({d[v],v});}}}
}int dp[N][55];
int vis[N][55];
int ok=0;int f(int x,int c)
{if(dp[x][c]!=-1) return dp[x][c];dp[x][c]=0,vis[x][c]=1;for(auto [u,w]: e1[x]){int res=d[x]-d[u]+c-w;if(res<0) continue;if(vis[u][res]) ok=1;dp[x][c]+=f(u,res);dp[x][c]%=p;}vis[x][c]=0;return dp[x][c];
}void solve()
{	cin>>n>>m>>k>>p;ok=0;for(int i=1;i<=n;i++) e1[i].clear(),e[i].clear();for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}dijk(1);memset(dp,-1,sizeof dp);dp[1][0]=1;ll ans=0;for(int i=0;i<=k;i++){ans+=f(n,i);ans%=p;}f(n,k+1);if(ok){cout<<-1<<endl;}else cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}