建一个反图跑个最短路，然后记忆化搜索一下。
（很迷的是堆优化dij就wa了，线段树优化的和spfa就A了。）（求dalao看看我的堆优化dij是不是打错了，但是过了80分）。
spfa的AC代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cctype>
#include <cstring>
using namespace std;
const int N=100005;
int T,n,m,K,p,ecnt,head[N],dis[N],fhead[N];
bool vis[N];
long long f[N][51];
bool inq[N][51];
struct Edge{int to,nxt,val;}e[N<<2];
void add(int bg,int ed,int val){e[++ecnt].nxt=head[bg];e[ecnt].to=ed;e[ecnt].val=val;head[bg]=ecnt;}
void add2(int bg,int ed,int val){e[++ecnt].nxt=fhead[bg];e[ecnt].to=ed;e[ecnt].val=val;fhead[bg]=ecnt;}
int rd() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct Node{bool operator ()(int x,int y) {return dis[x]>dis[y];}};
void dij(){
priority_queue<int,vector<int>,Node>q;
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
q.push(n);
dis[n]=0;
while(!q.empty()) {
int u=q.top();q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=fhead[u];i;i=e[i].nxt) {
int v=e[i].to;
dis[v]=min(dis[v],dis[u]+e[i].val);
q.push(v);
}
}
}
long long dp(int x,int k) {
if(inq[x][k]) return -1;
if(f[x][k]) return f[x][k];
inq[x][k]=1;if(x==n) f[x][k]=1;else f[x][k]=0;
for(int i=head[x];i;i=e[i].nxt) {
int v=e[i].to;
int tmp=dis[v]-dis[x]+e[i].val;
if(tmp<=k) {
int tp=dp(v,k-tmp);
if(tp==-1) return f[x][k]=-1;
f[x][k]=(f[x][k]+tp)%p;
}
}
inq[x][k]=0;
return f[x][k];
}
void spfa() {
memset(dis,0x3f,sizeof dis);
queue<int>q;
q.push(n);
vis[n]=1;dis[n]=0;
while(!q.empty()) {
int u=q.front();vis[u]=0;q.pop();
for(int i=fhead[u];i;i=e[i].nxt) {
int v=e[i].to;
if(dis[u]+e[i].val<dis[v]) {
dis[v]=dis[u]+e[i].val;
if(!vis[v]) q.push(v),vis[v]=1;
}
}
}
}
int main() {
T=rd();
while (T--) {
memset(f,0,sizeof f);memset(inq,0,sizeof inq);memset(head,0,sizeof head);memset(fhead,0,sizeof fhead);ecnt=0;
n=rd();m=rd();K=rd();p=rd();
for(int i=1,a,b,c;i<=m;i++)
a=rd(),b=rd(),c=rd(),add(a,b,c),add2(b,a,c);
spfa();
long long ans=dp(1,K);
printf("%lld
",ans);
}
}
堆优化的：
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cctype>
#include <cstring>
using namespace std;
const int N=100005;
int T,n,m,K,p,ecnt,head[N],dis[N],fhead[N];
bool vis[N];
long long f[N][51];
bool inq[N][51];
struct Edge{int to,nxt,val;}e[N<<2];
void add(int bg,int ed,int val){e[++ecnt].nxt=head[bg];e[ecnt].to=ed;e[ecnt].val=val;head[bg]=ecnt;}
void add2(int bg,int ed,int val){e[++ecnt].nxt=fhead[bg];e[ecnt].to=ed;e[ecnt].val=val;fhead[bg]=ecnt;}
int rd() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct Node{bool operator ()(int x,int y) {return dis[x]>dis[y];}};
void dij(){
priority_queue<int,vector<int>,Node>q;
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
q.push(n);
dis[n]=0;
while(!q.empty()) {
int u=q.top();q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=fhead[u];i;i=e[i].nxt) {
int v=e[i].to;
if(dis[u]+e[i].val>dis[v]) continue;
dis[v]=min(dis[v],dis[u]+e[i].val);
q.push(v);
}
}
}
long long dp(int x,int k) {
if(inq[x][k]) return -1;
if(f[x][k]) return f[x][k];
inq[x][k]=1;if(x==n) f[x][k]=1;else f[x][k]=0;
for(int i=head[x];i;i=e[i].nxt) {
int v=e[i].to;
int tmp=dis[v]-dis[x]+e[i].val;
if(tmp<=k) {
int tp=dp(v,k-tmp);
if(tp==-1) return f[x][k]=-1;
f[x][k]=(f[x][k]+tp)%p;
}
}
inq[x][k]=0;
return f[x][k];
}
int main() {
T=rd();
while (T--) {
memset(f,0,sizeof f);memset(inq,0,sizeof inq);memset(head,0,sizeof head);memset(fhead,0,sizeof fhead);ecnt=0;
n=rd();m=rd();K=rd();p=rd();
for(int i=1,a,b,c;i<=m;i++)
a=rd(),b=rd(),c=rd(),add(a,b,c),add2(b,a,c);
dij();
long long ans=dp(1,K);
printf("%lld
",ans);
}
}