luogu3953
solution：
一开始看到的时候最短路计数的时候还疑惑了一下
因为之前做的只有最小生成树计数，图上路径计数怎么搞啊
然后感觉是类似搜索的东西可以搞一搞
忍不住看了下标签：记忆化搜索
嗷！原来这样
但是一开始定义的f数组是一维的只记录点
但是立马就发现这样不行了
因为一个点可能有多种路长
但是路长太长了没法记啊
【搜索|记搜、最短路--NOIP2017 逛公园】所以我们应该要记比最短路多出去的那一部分呀！！！
因为k最大只有50哎呀这不就完了
这个我是倒着搜的，正着也能做
还有我们要判一下环，如果f[u][kk]已经被访问过了说明有0环
这个时候走多少次0环都可以，所以输出-1
然后可以算出下一个点要比最短路多出多少，根据这个dfs下一个点
如果f不是-1说明已经被dfs过了就返回这个值
很普通的记搜操作呀
然后就是初始化啊细节之类的问题了

#include #include #include #include #include #include #define N 100005 #define M 200005 using namespace std; int t,n,m,k,p,cnt,head[N],cnt2,head2[N],dis[N],f[N][55],ans; bool vis[N],flg,used[N][55]; priority_queue< pair > q; inline int rd(){ int x=0,f=1; char c=' '; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar(); } while(c<='9' && c>='0') x=x*10+c-'0',c=getchar(); return x*f; }struct EDGE{ int to,nxt,w; }edge[M],e[M]; void add(int x,int y,int z){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; edge[cnt].w=z; head[x]=cnt; }void add2(int x,int y,int z){ e[++cnt2].to=y; e[cnt2].nxt=head2[x]; e[cnt2].w=z; head2[x]=cnt2; }void dijkstra(){ memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); dis[1]=0; while(!q.empty()) q.pop(); q.push(make_pair(0,1)); while(!q.empty()){ int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=head[x]; i; i=edge[i].nxt){ int y=edge[i].to,z=edge[i].w; if(dis[y]>dis[x]+z) dis[y]=dis[x]+z,q.push(make_pair(-dis[y],y)); } } }int dfs(int u,int kk){ if(flg) return 0; if(u==n+1 && kk==0) return 1; if(f[u][kk]!=-1) return f[u][kk]; f[u][kk]=0; if(used[u][kk]) {flg=true; return 0; } used[u][kk]=1; for(int i=head2[u]; i; i=e[i].nxt){ int v=e[i].to; int nxk=kk+dis[u]-dis[v]-e[i].w; if(nxk>=0 && nxk<=k){ if(used[v][nxk]) {flg=true; return 0; } (f[u][kk]+=dfs(v,nxk))%=p; } } used[u][kk]=0; return f[u][kk]; }void init(){ memset(f,-1,sizeof f); ans=cnt=cnt2=0; memset(used,0,sizeof used); flg=false; memset(head,0,sizeof head); memset(head2,0,sizeof head2); }int main(){ t=rd(); while(t--){ init(); n=rd(); m=rd(); k=rd(); p=rd(); for(int i=1; i<=m; i++){ int x=rd(),y=rd(),z=rd(); add(x,y,z); add2(y,x,z); } dijkstra(); dis[n+1]=0; add2(1,n+1,0); //这里是因为1到n本来就有一条最短路 for(int i=0; i<=k; i++){ (ans+=dfs(n,i))%=p; if(flg) break; } if(flg) printf("-1\n"); else printf("%d\n",ans); } return 0; }

#include #include #include #include #include #include #include #include #include using namespace std; const int N=100010; const int inf=0x3f3f3f3f; typedef long long ll; inline int read(){ int r=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9'){r=r*10+c-'0'; c=getchar(); } return r*f; } struct Edge{ int to,nxt,w; }e[N*2],E[N*2]; int head[N],Head[N],cnt=1; void add(int u,int v,int w){ e[cnt]=(Edge){v,head[u],w}; head[u]=cnt; E[cnt]=(Edge){u,Head[v],w}; Head[v]=cnt++; } int n,m,K,P; bool inq[N]; int dis[N],f[N][51],c[N][51]; void spfa(){ dequeq; memset(dis,63,sizeof dis); dis[1]=0; q.push_back(1); inq[1]=1; while(!q.empty()){ int u=q.front(); q.pop_front(); inq[u]=0; for(int i=head[u]; i; i=e[i].nxt){ int v=e[i].to,w=e[i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; if(!inq[v]){ if(!q.empty()&&dis[v]<=dis[q.front()]) q.push_front(v); else q.push_back(v); } } } } }bool ff=0; void Clear(){ n=m=K=P=0; memset(inq,0,sizeof inq); memset(f,-1,sizeof f); memset(head,0,sizeof head); memset(Head,0,sizeof Head); memset(c,0,sizeof c); memset(e,0,sizeof e); memset(E,0,sizeof E); cnt=1; ff=0; } void Init(){ n=read(),m=read(),K=read(),P=read(); while(m--){ int u=read(),v=read(),w=read(); add(u,v,w); } }int dfs(int u,int k){ if(~f[u][k])return f[u][k]; c[u][k]=1; f[u][k]=0; for(int i=Head[u]; i; i=E[i].nxt){ int v=E[i].to,w=E[i].w; int t=dis[u]+k-w-dis[v]; if(t<0)continue; if(c[v][t])ff=1; f[u][k]+=dfs(v,t),f[u][k]%=P; } c[u][k]=0; return f[u][k]; } void Solve(){ spfa(); f[1][0]=1; int ans=0; for(int j=0; j<=K; j++) ans+=dfs(n,j),ans%=P; dfs(n,K+1); if(ff){ cout<<-1<