NOIp2017 Day1T3 逛公园（SPFA+记忆化DP）
Posted On 2017年12月29日
Description
Solution
对于30%的数据，显然可以SPFA后暴力DFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <cstdio> #include <cstring> #define ll long long inline int read() { register int f=1,k=0;register char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1e6*2+100; struct mc{ int too,nxt,co; }e[maxn]; ll la[maxn],dist[maxn],q[maxn*5]; bool v[maxn]; int n,m,k,p; ll ans; void spfa() { memset(dist,0x7f,sizeof(dist)); memset(v,0,sizeof(v)); dist[1]=0; q[1]=1;register int h=1,t=1; while (h<=t) { for (register int i=la[q[h]];i;i=e[i].nxt) if (dist[e[i].too]>dist[q[h]]+e[i].co) { dist[e[i].too]=dist[q[h]]+e[i].co; if (!v[e[i].too])q[++t]=e[i].too,v[e[i].too]=1; } v[q[h]]=0; h++; } } void dfs(int cur,int curco) { if (cur==n){ans++;return;} for (register int i=la[cur];i;i=e[i].nxt) if (k+dist[n]>=e[i].co+curco)dfs(e[i].too,curco+e[i].co); } void work() { memset(la,0,sizeof(la)); n=read(),m=read(),k=read(),p=read(); for (register int i=1,a,b,c;i<=m;i++) { a=read(),b=read(),c=read(); e[i].nxt=la[a]; la[a]=i; e[i].too=b; e[i].co=c; } spfa(); ans=0; dfs(1,0); printf("%lld\n",ans%p); } int main() { int t=read(); while (t--)work(); } |
对于100%的数据
SPFA+记忆化DP
时间复杂度
如果没有零环，从终点倒序记忆化DP即可
考虑在最短路+k内的零环：如当前DFS中，符合条件(vis[e[i].too][k])的点被再次遍历return -1即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <bits/stdc++.h> inline int read() { register int f=1,k=0;register char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1e5+100,maxm=maxn<<1; bool v[maxn],flag,vis[maxn][51]; int n,m,k,P,dist[maxn],last[maxn],Last[maxn],q[maxm<<2],ans,f[maxn][51]; struct mc{int to,nxt,co;}e[maxm],E[maxm]; inline void spfa() { int head=1,rear=1; q[1]=1;v[1]=1; while (head<=rear) { for (register int i=last[q[head]];i;i=e[i].nxt) if (dist[e[i].to]>dist[q[head]]+e[i].co) dist[e[i].to]=dist[q[head]]+e[i].co,!v[e[i].to]&&(v[e[i].to]=1,q[++rear]=e[i].to); v[q[head++]]=0; } } int dfs(const int u,const int k) { if (~f[u][k])return f[u][k]; vis[u][k]=1;f[u][k]=0; for (register int i=Last[u],tmp;i;i=E[i].nxt) { tmp=dist[u]-dist[E[i].to]-E[i].co+k; if (tmp<0)continue; if (vis[E[i].to][tmp])flag=1; f[u][k]=(f[u][k]+dfs(E[i].to,tmp))%P; } vis[u][k]=0; return f[u][k]; } int main() { for (int T=read();T;T--) { memset(last,0,sizeof(last)); memset(Last,0,sizeof(Last)); memset(f,-1,sizeof(f));f[1][0]=1; memset(dist,0x7f,sizeof(dist));dist[1]=0; n=read(),m=read(),k=read(),P=read(); for (register int i=1,a,b;i<=m;i++) e[i].nxt=last[a=read()],last[a]=i,e[i].to=b=read(), E[i].co=e[i].co=read(),E[i].nxt=Last[b],Last[b]=i,E[i].to=a; memset(v,0,sizeof(v));spfa();memset(vis,0,sizeof(vis));ans=0;flag=0; for (register int i=0;i<=k;i++)ans=(ans+dfs(n,i))%P; printf("%d\n",!flag?ans:-1); } } |
Subscribe
0 评论