代码

#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=100005,M=200005,K=55,INF=0x3f3f3f3f;
int n,m,k,md,t,u,v,ww,top;
bool ok;
int first[N],next[M],end[M],w[M],rfirst[N],rnext[M],rend[M],rw[M];
int d[N],rd[N],f[N][K],st[N*K],stj[N*K];
bool done[N],ini[N][K];
struct node
{
    int d,id;
};
bool operator < (node a,node b)
{
    if(a.d==b.d)
        return a.id>b.id;
    return a.d>b.d;
}
priority_queue<node>q;
inline void addedge(int u,int v,int ww,int i)
{
    next[i]=first[u];
    first[u]=i;
    end[i]=v;
    w[i]=ww;
}
inline void raddedge(int u,int v,int ww,int i)
{
    rnext[i]=rfirst[u];
    rfirst[u]=i;
    rend[i]=v;
    rw[i]=ww;
}
inline void rdijkstra()
{
    memset(rd,0x3f,sizeof(d));
    memset(done,0,sizeof(done));
    rd[n]=0;
    q.push((node){0,n});
    while(!q.empty())
    {
        int x=q.top().id;
        q.pop();
        if(done[x])
            continue;
        done[x]=1;
        for(int j=rfirst[x];j!=0;j=rnext[j])
            if(rd[rend[j]]>rd[x]+rw[j])
            {
                rd[rend[j]]=rd[x]+rw[j];
                q.push((node){rd[rend[j]],rend[j]});
            }
    }
}
inline void dijkstra()
{
    ok=1;
    memset(d,0x3f,sizeof(d));
    memset(done,0,sizeof(done));
    d[1]=0;
    q.push((node){0,1});
    while(!q.empty())
    {
        int x=q.top().id;
        q.pop();
        if(done[x])
            continue;
        done[x]=1;
        for(int j=first[x];j!=0;j=next[j])
            if(d[end[j]]>d[x]+w[j])
            {
                d[end[j]]=d[x]+w[j];
                q.push((node){d[end[j]],end[j]});
            }
    }
}
int dfs(int u,int k)
{
    if(f[u][k]!=-1)
    {
        if(ini[u][k])
            ok=0;
        return f[u][k];
    }
    ini[u][k]=1;
    f[u][k]=u==n;
    for(int j=first[u];j!=0&&ok;j=next[j])
        if(rd[end[j]]!=INF&&rd[u]!=INF)
        {
            if(rd[end[j]]+w[j]<rd[u])
                return 0;
            if(rd[end[j]]+w[j]==rd[u])
                f[u][k]=(f[u][k]+dfs(end[j],k))%md;
            else if(rd[end[j]]+w[j]>rd[u]&&rd[end[j]]+w[j]-rd[u]<=k)
                f[u][k]=(f[u][k]+dfs(end[j],k-(w[j]-rd[u]+rd[end[j]])))%md;
        }
    ini[u][k]=0;
    //printf("%d %d %d\n",u,k,f[u][k]);
    return f[u][k];
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&m,&k,&md);
        memset(first,0,sizeof(first));
        memset(next,0,sizeof(next));
        memset(end,0,sizeof(end));
        memset(rfirst,0,sizeof(rfirst));
        memset(rnext,0,sizeof(rnext));
        memset(rend,0,sizeof(rend));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&ww);
            addedge(u,v,ww,i);
            raddedge(v,u,ww,i);
        }
        ok=1;
        dijkstra();
        rdijkstra();
        memset(f,-1,sizeof(f));
        dfs(1,k);
        if(!ok)
        {
            printf("-1\n");
            continue;
        }
        printf("%d\n",f[1][k]);
    }
    return 0;
}

评测结果