用了vector 70分 最后3点TLE..
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int val,to;
};
vector<Node> h[200005],h1[200005];
int dis[200005];
queue<int> q;
int n;
void spfa()
{
dis[n]=0;
q.push(n);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0;i<h1[x].size();++i)
{
int v=h1[x][i].to;
if(dis[v]>dis[x]+h1[x][i].val)
{
dis[v]=dis[x]+h1[x][i].val;
q.push(v);
}
}
}
}
int p,f[200005][55],vis[200005][55],flag;
int dfs(int x,int k) //k：偏移量
{
if(flag) return 0;
if(vis[x][k])
{
flag=1;
return 0;
}
if(f[x][k]>0) return f[x][k];
vis[x][k]=1;
int sum=0;
for(int i=0;i<h[x].size();++i)
{
int t=k-(dis[h[x][i].to]-dis[x]+h[x][i].val);
if(t>k || t<0) continue;
sum+=dfs(h[x][i].to,t);
sum%=p;
if(flag) return 0;
}
vis[x][k]=0;
if(x==n && k==0) sum=1;
f[x][k]=sum;
return f[x][k];
}
int read()
{
int x=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
int main()
{
int t;
t=read();
while(t--)
{
Node c;
int m,k;
memset(f,-1,sizeof(f));
memset(dis,0x3f,sizeof(dis));
flag=0;
n=read(); m=read(); k=read(); p=read();
for(int i=1;i<=n;++i)
h[i].clear(),h1[i].clear();
for(int i=1;i<=m;++i)
{
int x,y,z;
x=read(); y=read(); z=read();
c.to=y; c.val=z;
h[x].push_back(c);
c.to=x;
h1[y].push_back(c);
}
spfa();
int ans=0;
for(int i=0;i<=k;++i)
{
memset(vis,0,sizeof(vis));
int ck=dfs(1,i);
if(flag) break;
ans=(ans+ck)%p;
}
if(flag)
{
printf("-1\n");
continue;
}
printf("%d\n",ans);
}
return 0;
}
```
by ⑨baka @ 2019-03-30 00:16:50
哇塞，是baka欸
by Jameswood @ 2019-03-30 01:04:43
@[⑨baka](/space/show?uid=90285) orz大佬重出江湖
by ShineEternal @ 2019-03-30 06:33:24
催更催更！！！
by dblark @ 2019-03-30 06:59:20
催更
by ez_lcw @ 2019-03-30 07:08:13
不清楚诶，我的记搜只有4126ms..
by Sai0511 @ 2019-03-30 07:37:03
稍微改了一下 目前10000ms左右
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int val,to;
};
vector<Node> h[200005],h1[200005];
int dis[200005];
queue<int> q;
int n;
void spfa()
{
dis[n]=0;
q.push(n);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0;i<h1[x].size();++i)
{
int v=h1[x][i].to;
if(dis[v]>dis[x]+h1[x][i].val)
{
dis[v]=dis[x]+h1[x][i].val;
q.push(v);
}
}
}
}
int p,f[200005][55],vis[200005][55],flag;
int dfs(int x,int k) //k：偏移量
{
if(flag) return 0;
if(vis[x][k])
{
flag=1;
return 0;
}
if(f[x][k]>0) return f[x][k];
vis[x][k]=1;
int sum=0;
for(int i=0;i<h[x].size();++i)
{
int t=k-(dis[h[x][i].to]-dis[x]+h[x][i].val);
if(t>k || t<0) continue;
int ck=dfs(h[x][i].to,t);
sum=(sum+ck)%p;
if(flag) return 0;
}
vis[x][k]=0;
if(x==n && k==0) sum=1;
f[x][k]=sum;
return f[x][k];
}
int read()
{
int x=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
int main()
{
int t;
t=read();
while(t--)
{
Node c;
int m,k;
memset(f,-1,sizeof(f));
memset(dis,0x3f,sizeof(dis));
flag=0;
n=read(); m=read(); k=read(); p=read();
for(int i=1;i<=n;++i)
h[i].clear(),h1[i].clear();
for(int i=1;i<=m;++i)
{
int x,y,z;
x=read(); y=read(); z=read();
c.to=y; c.val=z;
h[x].push_back(c);
c.to=x;
h1[y].push_back(c);
}
spfa();
int ans=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<=k;++i)
{
// memset(vis,0,sizeof(vis));
int ck=dfs(1,i);
if(flag) break;
ans=(ans+ck)%p;
}
if(flag)
{
printf("-1\n");
continue;
}
printf("%d\n",ans);
}
return 0;
}
```
by ⑨baka @ 2019-03-30 17:25:32
把0-k循环这段去掉了 然后就A了...
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int val,to;
};
vector<Node> h[200005],h1[200005];
int dis[200005];
queue<int> q;
int n;
void spfa()
{
dis[n]=0;
q.push(n);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=0;i<h1[x].size();++i)
{
int v=h1[x][i].to;
if(dis[v]>dis[x]+h1[x][i].val)
{
dis[v]=dis[x]+h1[x][i].val;
q.push(v);
}
}
}
}
int p,f[200005][55],vis[200005][55],flag;
int dfs(int x,int k) //k：偏移量
{
if(flag) return 0;
if(vis[x][k])
{
flag=1;
return 0;
}
if(f[x][k]>0) return f[x][k];
vis[x][k]=1;
if(x==n) f[x][k]=1;
else f[x][k]=0;
for(int i=0;i<h[x].size();++i)
{
int t=k-(dis[h[x][i].to]-dis[x]+h[x][i].val);
if(t>k || t<0) continue;
int ck=dfs(h[x][i].to,t);
f[x][k]=(f[x][k]+ck)%p;
if(flag) return 0;
}
vis[x][k]=0;
return f[x][k];
}
int read()
{
int x=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
int main()
{
int t;
t=read();
while(t--)
{
Node c;
int m,k;
memset(f,-1,sizeof(f));
memset(dis,0x3f,sizeof(dis));
flag=0;
n=read(); m=read(); k=read(); p=read();
for(int i=1;i<=n;++i)
h[i].clear(),h1[i].clear();
for(int i=1;i<=m;++i)
{
int x,y,z;
x=read(); y=read(); z=read();
c.to=y; c.val=z;
h[x].push_back(c);
c.to=x;
h1[y].push_back(c);
}
spfa();
int ans=0;
memset(vis,0,sizeof(vis));
ans=dfs(1,k);
ans%=p;
if(flag)
{
printf("-1\n");
continue;
}
printf("%d\n",ans);
}
return 0;
}
```
by ⑨baka @ 2019-03-30 17:38:56