代码

// NOIP2017 逛公园 - layered DP + Dijkstra
// JudgeDuck direct memory IO
#include <sys/auxv.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

static inline DuckInfo* duck(){ return (DuckInfo*)getauxval(0x6b637564ULL); }

static const char* RP; static const char* RE;
static inline int rd(){
  int x=0;
  while(RP<RE && (unsigned char)*RP <= ' ') RP++;
  while(RP<RE && (unsigned char)*RP >= '0' && (unsigned char)*RP <= '9'){ x=x*10+((*RP)-'0'); RP++; }
  return x;
}

static char* WP;
static inline void wr(int x){
  if(x<0){ *WP++='-'; x=-x; }
  char t[12]; int n=0;
  if(x==0) t[n++]='0';
  while(x){ t[n++]='0'+(x%10); x/=10; }
  while(n--) *WP++=t[n];
}

static const int MAXN = 100005;
static const int MAXM = 200005;
static const int INF = 0x3f3f3f3f;

static int d[MAXN], f[MAXN];
static int fh[MAXN], fto[MAXM], fw[MAXM], fnxt[MAXM];
static int rh[MAXN], rto[MAXM], rw[MAXM], rnxt[MAXM];
static int zih[MAXN], zi_from[MAXM], zi_nxt[MAXM];
static int zoh[MAXN], zo_to[MAXM], zo_nxt[MAXM];
static int indeg[MAXN];
static char active[MAXN];
static int zorder[MAXN];
static int q[MAXN];
static int pu[MAXM], pv[MAXM], pd[MAXM];
static int dp[MAXN*52];
static int hd[MAXN], hn[MAXN], hs;

static inline void hpush(int nd, int v){
  int i=++hs;
  while(i>1){ int p=i>>1; if(hd[p]<=nd) break; hd[i]=hd[p]; hn[i]=hn[p]; i=p; }
  hd[i]=nd; hn[i]=v;
}

static void dijkstra(int n, int src, int* dist, int* head, int* to, int* w, int* nxt){
  for(int i=0;i<=n;i++) dist[i]=INF;
  dist[src]=0; hs=1; hd[1]=0; hn[1]=src;
  while(hs){
    int du=hd[1], u=hn[1];
    int lastd=hd[hs], lastn=hn[hs]; hs--;
    { int i=1; while(1){ int l=i<<1, r=l|1, s=i;
        if(l<=hs && hd[l]<hd[s]) s=l;
        if(r<=hs && hd[r]<hd[s]) s=r;
        if(s==i) break; hd[i]=hd[s]; hn[i]=hn[s]; i=s; }
      hd[i]=lastd; hn[i]=lastn; }
    if(du!=dist[u]) continue;
    for(int e=head[u];e!=-1;e=nxt[e]){
      int v=to[e]; int nd=du+w[e];
      if(nd<dist[v]){ dist[v]=nd; hpush(nd,v); }
    }
  }
}

static int solve(int n, int m, int K, int P){
  for(int i=0;i<=n;i++){ fh[i]=-1; rh[i]=-1; }
  for(int e=0;e<m;e++){
    int u=rd(), v=rd(), w=rd();
    fto[e]=v; fw[e]=w; fnxt[e]=fh[u]; fh[u]=e;
    rto[e]=u; rw[e]=w; rnxt[e]=rh[v]; rh[v]=e;
  }
  dijkstra(n,1,d,fh,fto,fw,fnxt);
  dijkstra(n,n,f,rh,rto,rw,rnxt);
  if(d[n]>=INF) return 0;
  long long LIM=(long long)d[n]+K;
  int numActive=0;
  for(int v=1;v<=n;v++){
    bool a=(d[v]<INF && f[v]<INF && (long long)d[v]+(long long)f[v]<=LIM);
    active[v]=a; if(a) numActive++;
  }
  for(int v=1;v<=n;v++){ zoh[v]=-1; zih[v]=-1; indeg[v]=0; }
  int zc=0, pc=0;
  for(int u=1;u<=n;u++){
    if(!active[u]) continue;
    for(int e=fh[u];e!=-1;e=fnxt[e]){
      int v=fto[e]; if(!active[v]) continue;
      int w=fw[e];
      int delta=d[u]+w-d[v];
      if(delta==0){
        zo_to[zc]=v; zo_nxt[zc]=zoh[u]; zoh[u]=zc;
        zi_from[zc]=u; zi_nxt[zc]=zih[v]; zih[v]=zc;
        zc++; indeg[v]++;
      } else if(delta<=K){
        pu[pc]=u; pv[pc]=v; pd[pc]=delta; pc++;
      }
    }
  }
  int qh=0, qt=0;
  for(int v=1;v<=n;v++) if(active[v] && indeg[v]==0) q[qt++]=v;
  int processed=0;
  while(qh<qt){
    int u=q[qh++]; zorder[processed++]=u;
    for(int e=zoh[u];e!=-1;e=zo_nxt[e]){ int v=zo_to[e]; if(--indeg[v]==0) q[qt++]=v; }
  }
  if(processed<numActive) return -1;

  int W=K+1;
  int total=(n+1)*W;
  memset(dp,0,sizeof(int)*total);
  dp[W+0]=1%P; // node 1, k=0
  for(int k=0;k<=K;k++){
    for(int i=0;i<pc;i++){
      int dd=pd[i]; if(dd>k) continue;
      int u=pu[i], v=pv[i];
      int x=dp[v*W+k]+dp[u*W+(k-dd)];
      if(x>=P) x-=P;
      dp[v*W+k]=x;
    }
    for(int t=0;t<processed;t++){
      int v=zorder[t];
      int* sv=dp+v*W;
      for(int e=zih[v];e!=-1;e=zi_nxt[e]){
        int u=zi_from[e];
        int* su=dp+u*W;
        int x=sv[k]+su[k];
        if(x>=P) x-=P;
        sv[k]=x;
      }
    }
  }
  long long ans=0;
  for(int k=0;k<=K;k++) ans+=dp[n*W+k];
  ans%=P;
  return (int)ans;
}

int main(){
  DuckInfo* dk=duck();
  static char lbuf[1<<22];
  if(dk && dk->stdin_ptr){ RP=dk->stdin_ptr; RE=dk->stdin_ptr+dk->stdin_size; }
  else { size_t n=fread(lbuf,1,sizeof(lbuf),stdin); RP=lbuf; RE=lbuf+n; }
  static char obuf[1<<16];
  if(dk && dk->stdout_ptr){ WP=dk->stdout_ptr; } else { WP=obuf; }
  int T=rd();
  while(T--){
    int n=rd(), m=rd(), K=rd(), P=rd();
    int a=solve(n,m,K,P);
    wr(a); *WP++='\n';
  }
  if(dk && dk->stdout_ptr){ dk->stdout_size=(uint64_t)(WP-dk->stdout_ptr); }
  else { fwrite(obuf,1,WP-obuf,stdout); fflush(stdout); }
  asm volatile("mov $60,%%eax; xor %%edi,%%edi; syscall" ::: "rax","rdi","memory");
  return 0;
}

评测结果