题目来源：洛谷P3953
思路
先用SPFA求一遍最短路
在求最短路的同时可以把所有点到终点的最短路求出来 dis数组
注意要反向SPFA 因为从起点开始可能会走到一些奇怪的路上导致时间负责度增加
我们定一个f[u][k]数组为从当前节点u还剩时间k到达终点的方案
原来从u走到终点的最短路径消耗时间为dis[u]
而我们现在考虑走(u,v,w)这条边（不是最短路）
那么比走最短路需要多dis[v]+w-dis[u]的时间
所以f[u][k]=∑f[v][k-(dis[v]+w-dis[u])] （从u到终点上有另一个点v）
记忆化搜索即可
PS：容易错的地方是没有初始化
代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 100010
#define INF 1e9+7
int T,n,m,k,p,cnt,limit,ans;
int dis[maxn],h1[maxn],h2[maxn],f[maxn][
55];
bool vis[maxn],v[maxn][
55];
struct Edge
{
int to;
int next;
int w;
}e1[maxn*
2],e2[maxn*
2];
void add(
int u,
int v,
int w)
{
e1[++cnt].to=
v;
e1[cnt].w=
w;
e1[cnt].next=
h1[u];
h1[u]=
cnt;
e2[cnt].to=
u;
e2[cnt].w=
w;
e2[cnt].next=
h2[v];
h2[v]=
cnt;
}
void spfa()
//反向SPFA
{
queue<
int>
q;
memset(vis,0,
sizeof(vis));
for(
int i=
1;i<=n;i++) dis[i]=
INF;
q.push(n);
dis[n]=
0;
vis[n]=
1;
while(!
q.empty())
{
int temp=
q.front();
q.pop();
vis[temp]=
0;
for(
int i=h2[temp];i;i=
e2[i].next)
{
int v=
e2[i].to;
if(dis[v]>dis[temp]+
e2[i].w)
{
dis[v]=dis[temp]+
e2[i].w;
if(!
vis[v])
{
vis[v]=
1;
q.push(v);
}
}
}
}
}
int dfs(
int u,
int k)
{
if(v[u][k])
return -
1;
//如果一条路上一个点第二次到达 说明有环
if(f[u][k])
return f[u][k];
//记忆化
v[u][k]=
1;
if(u==n) f[u][k]=
1;
//边界条件 到达终点还剩k步方案数为1
else f[u][k]=
0;
//否则为0
for(
int i=h1[u];i;i=
e1[i].next)
{
int v=
e1[i].to;
int temp=dis[v]-dis[u]+e1[i].w;
//判断每一条路相比最短路是否超过k
if(temp<=k)
//没超过
{
int w=dfs(v,k-temp);
//继续dfs 记得减去剩余时间
if(w==-
1)
return f[u][k]=-
1;
f[u][k]=(f[u][k]+w)%p;
//记录方案数
}
}
v[u][k]=
0;
//重置点
return f[u][k];
}
int main()
{
cin>>
T;
while(T--
)
{
cnt=
0,ans=
0;
memset(h1,0,
sizeof(h1));
//记得初始化
memset(h2,
0,
sizeof(h2));
memset(f,0,
sizeof(f));
memset(v,0,
sizeof(v));
cin>>n>>m>>k>>
p;
for(
int i=
1;i<=m;i++
)
{
int x,y,z;
cin>>x>>y>>
z;
add(x,y,z);
}
spfa();
cout<<dfs(
1,k)<<endl;
//ans在dfs(1,k)中
}
}
转载于:https://www.cnblogs.com/BrokenString/p/9871549.html
