解题报告

吃我一记万年神坑。考场上我想到了 $f_{i,j}$ 表示到 $i$ 点比最短路多 $j$ 的方案数，但是我不会转移，写了玄学转移骗了60。

不会转移？记忆化搜索大法吼啊，令 $dis_i$ 表示 $1$ 到 $i$ 的最短路，那么：

$$ f_{i,k}=\sum_{(j,i)\in E}f_{j,k-(dis_j+w_{i,j}-dis_i)} $$

从 $f_{n,i}$ 开始搜索就行了。现在唯一的问题就是 $0$ 环，实际上就是在记忆化搜索的过程中某个状态出现了两次就说明出现了 $0$ 环。为了防止最短路为 $0$ 的特殊情况，可以刷一遍 $f_{n,K+1}$ 。

示例程序

我怕你卡Spfa结果你告诉我你卡Dijkstra？假的，我写萎了。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000,maxm=200000,maxk=50;

int te,n,m,K,MOD,f[maxn+5][maxk+5],dis[maxn+5],ans;
int E,lnk[2][maxn+5],nxt[(maxm<<1)+5],son[(maxm<<1)+5],w[(maxm<<1)+5];
int si;pair<int,int> Heap[maxm+5];bool vis[maxn+5][maxk+5],fl;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(ID,x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[ID][x],lnk[ID][x]=E)
#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si))
#define Pop() (pop_heap(Heap+1,Heap+1+si--))
inline void Dij(int s){
    memset(dis,63,sizeof(dis));dis[s]=0;si=0;Push(mp(0,s));
    while (si){
        int x=Heap[1].sc,y=-Heap[1].fr;Pop();while (si&&dis[x]<y) x=Heap[1].sc,y=-Heap[1].fr,Pop();
        for (int j=lnk[0][x];j;j=nxt[j]) if (dis[x]+w[j]<dis[son[j]]) dis[son[j]]=dis[x]+w[j],Push(mp(-dis[son[j]],son[j]));
    }
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int DP(int x,int k){
    if (!fl) return -1;if (~f[x][k]) return f[x][k];vis[x][k]=true;f[x][k]=0;
    for (int j=lnk[1][x];j;j=nxt[j]){
        int now=k-(dis[son[j]]+w[j]-dis[x]);if (now<0) continue;
        if (vis[son[j]][now]) return fl=false,-1;AMOD(f[x][k],DP(son[j],now));
    }vis[x][k]=false;return f[x][k];
}
int main(){
    for (readi(te);te;te--){
        readi(n);readi(m);readi(K);readi(MOD);E=0;memset(lnk,0,sizeof(lnk));
        for (int i=1,x,y,z;i<=m;i++) readi(x),readi(y),readi(z),Add(0,x,y,z),Add(1,y,x,z);
        Dij(1);memset(f,255,sizeof(f));memset(vis,0,sizeof(vis));f[1][0]=1;ans=0;fl=true;DP(n,1);
        for (int k=0;fl&&k<=K;k++) AMOD(ans,DP(n,k));if (!fl) puts("-1"); else printf("%d\n",ans);
    }return 0;
}