毒瘤的noip2017
不过今年再来看。感觉容易许多。不再是无从下手了、希望今年也是吧
第一天的dp？ 就是这个。
看到k值不大，而且对答案有影响。那么就需要记录。
来看k的意义，是说比最短路多k。启示我们要求最短路。
可以类比一下(A^*)求k短路。先反向跑一边最短路作为估价函数，然后在正向跑。
这个题也可以如此做。只不过成了k短路计数。
然后dp的状态就很容易设计出来了。
设(f[i][j])表示从起点到了i这个点，多走了j的冤枉路。
转移呢，就是根据相邻两点分别到终点的最短路，计算又多走了多少的冤枉路。然后加进答案里。
那么无限多中答案是为什么呢？很容易就想到了零环。
然后如何判断零环呢？ 方法很多，可以预先跑dfs，拓扑排序，或者是在记忆化搜索时检查是否在栈中。
这里使用了拓扑排序（其实另外两个都试过，调了好久，没有错，最后发现，领接表忘清零了。拓扑排序是最后一个写的233）
只计算零边的对点产生的度数。然后把所有点压进容器（写法不同），然后只拓展零边。最后看是否所有点都被访问过。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using std::queue;
const int maxn=101000;
struct node
{
int p;
int value;
int nxt;
};
int h[maxn],H[maxn],tail;
node l[maxn<<2],L[maxn<<5];
int dis[maxn];
int n,m,k;
long long p;
bool inque[maxn];
void add(int a,int b,int c)
{
++tail;
l[tail].p=b;
l[tail].value=c;
l[tail].nxt=h[a];
h[a]=tail;
L[tail].p=a;
L[tail].value=c;
L[tail].nxt=H[b];
H[b]=tail;
}
void spfa()
{
memset(dis,127,sizeof(dis));
queue<int>q;
q.push(1);inque[1]=true;dis[1]=0;
while(!q.empty())
{
int pas=q.front();q.pop();
inque[pas]=false;
for(int i=h[pas];i;i=l[i].nxt)
{
int v=l[i].p;
if(dis[v]>dis[pas]+l[i].value)
{
dis[v]=dis[pas]+l[i].value;
if(!inque[v])
{
inque[v]=true;
q.push(v);
}
}
}
}
}
int ind[maxn];
bool vis[maxn];
bool topsort()
{
queue<int>q;
for(int i=1;i<=n;i++) if(!ind[i]) q.push(i);
while(!q.empty())
{
int pas=q.front();q.pop();
vis[pas]=true;
for(int i=h[pas];i;i=l[i].nxt)
if(!l[i].value&&!vis[l[i].p])
{
int v=l[i].p;
ind[v]--;
if(!ind[v])
q.push(v);
}
}
bool F=true;
for(int i=1;i<=n;i++)
if(!vis[i])
F=false;
return F;
}
long long f[maxn][60];
int dfs(int now,int K)
{
if(f[now][K]!=-1) return f[now][K];
f[now][K]=0;
for(int i=H[now];i;i=L[i].nxt)
{
int v=L[i].p;
int nxt=K-(dis[v]+L[i].value-dis[now]);
if(nxt<0||nxt>k) continue;
f[now][K]=(f[now][K]+dfs(v,nxt))%p;
}
return f[now][K];
}
void init()
{
memset(inque,0,sizeof(inque));
memset(vis,0,sizeof(vis));
//memset(V,0,sizeof(V));
memset(f,-1,sizeof(f));
memset(h,0,sizeof(h));
memset(H,0,sizeof(H));
memset(ind,0,sizeof(ind));
//tail=0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d%d%d%lld",&n,&m,&k,&p);
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
if(!c) ind[b]++;
}
if(!topsort())
{
printf("-1
");
continue;
}
spfa();
long long ans=0;
f[1][0]=1;
for(int i=0;i<=k;i++)
ans=(ans+dfs(n,i))%p;
printf("%lld
",ans);
}
}