NOIP2017 提高 luogu 3953 逛公园

NOIP2017 提高 luogu 3953 逛公园

​​ 题目背景 注 数据重造完了 题目描述 策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图，且没有 自环和重边。其中1号点是公园的入口，N号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从1号点进去，从N号点出来。 策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到N号点的最短路长为d，那么策策只会喜欢长度不超过d+K的路线。 策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？ 为避免输出过大，答案对P取模。 如果有无穷多条合法的路线，请输出−1。 输入输出格式 输入格式： 第一行包含一个整数 T, 代表数据组数。 接下来T组数据，对于每组数据： 第一行包含四个整数 N,M,K,P，每两个整数之间用一个空格隔开。 接下来M行，每行三个整数ai​,bi​,ci​，代表编号为ai​,bi​的点之间有一条权值为 ci​的有向边，每两个整数之间用一个空格隔开。 输出格式： 输出文件包含 T 行，每行一个整数代表答案。 输入输出样例 输入样例#1： 复制 2 5 7 2 10 1 2 1 2 4 0 4 5 2 2 3 2 3 4 1 3 5 2 1 5 3 2 2 0 10 1 2 0 2 1 0 输出样例#1： 复制 3 -1 说明 【样例解释1】 对于第一组数据，最短路为 3。 1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 为 3 条合法路径。 【测试数据与约定】 对于不同的测试点，我们约定各种参数的规模不会超过如下 测试点编号　　 T　　　 N　　　 M　　　 K　　　 是否有0边 1 5 5 10 0 否 2 5 1000 2000 0 否 3 5 1000 2000 50 否 4 5 1000 2000 50 否 5 5 1000 2000 50 否 6 5 1000 2000 50 是 7 5 100000 200000 0 否 8 3 100000 200000 50 否 9 3 100000 200000 50 是 10 3 100000 200000 50 是 对于 100%的数据, 1≤P≤109,1≤ai​,bi​≤N,0≤ci​≤1000。 数据保证：至少存在一条合法的路线。 题意： 题目要求我们找出1~n的最短路 然后 求出在长度浮动在k范围内的路径条数 首先 加入k=0并且不存在0环那这就是个最短路计数问题 考虑k<=50那么这题显然需要dp dp满足的条件是什么 就是我前面需要枚举的状态我都已经求解过了 而且 因为存在0环 所以我们需要先将0环排除掉 首先我们正着一遍dijkstra 反着一遍dijkstra 然后分别求出1到任意点的最短路 求出n到任一点的最短路 然后 我o(m)枚举所有的边 去比较是否这个边压根就不可能被我所统计到 那么可以这样来看我枚举一条边1~左边+权值+右边～n如果大于我最短路+k显然这条路径在计算的时候压根就不存在 所以删去 假如不删去的话我要新记录一个数组w[i]表示我i号边 因为我强制走这条边 导致我需要多花费的代价是多少 这时候 还有0环怎么搞 leoly（orz)的做法就是tarjan缩点来一波 看是否存在0环 存在输出-1否则继续 接下来 为了dp我们需要满足前面的都做过 当k=0的时候显然dijkstra的贪心思想已经满足了我们的要求 但是现在每个点被拆成了K个点 这样的话就不一定满足了 昨天已经有大佬秒出了 那么显然我们需要每次从入度为0的点去做 所以我们将这些点拓扑排序 然后从入度为0的点去转移即可 最后统计答案的时候把所有的可能性都加入输出即可

#include#include#include#include#include#define M 220000#define N 110000#define pa pairusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int x,y,next,z;}data1[M],data[M];int f[N],f1[N],flag[N],mark[M],h1[N],h[N],num,dfn[N],low[N],size[N],s,in[N][55],dp[N][55],w[M],T,n,m,k,p,stackf[N];inline void dijkstra(){ priority_queue,greater >q;memset(f,0x3f,sizeof(f));f[1]=0; memset(flag,0,sizeof(flag));q.push(make_pair(0,1)); while(!q.empty()){ int x=q-().second;q.pop();if (flag[x]) continue;flag[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (f[x]+z,greater >q;memset(flag,0,sizeof(flag));memset(f1,0x3f,sizeof(f1)); q.push(make_pair(0,n));f1[n]=0; while(!q.empty()){ int x=q-().second;q.pop();if (flag[x]) continue;flag[x]=1; for (int i=h1[x];i;i=data1[i].next){ int y=data1[i].y,z=data1[i].z; if (f1[x]+zq;void tarjan(int x){ dfn[x]=++num;low[x]=num;q.push(x);stackf[x]=1; for (int i=h[x];i;i=data[i].next){ if (mark[i]||data[i].z) continue; int y=data[i].y; if (!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if (stackf[y]) low[x]=min(low[x],low[y]); } if (dfn[x]==low[x]){ int y;s++;size[s]=0; do{ y=q-();stackf[y]=0;q.pop();size[s]++; }while(y!=x); }}int main(){ freopen("3953.in","r",stdin); T=read(); while(T--){ n=read();m=read();k=read();p=read();num=0;memset(mark,0,sizeof(mark)); memset(h,0,sizeof(h));memset(h1,0,sizeof(h1)); for (int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;data[i].x=x; data1[num].y=x;data1[num].z=z;data1[num].next=h1[y];h1[y]=num;data1[i].x=y; } dijkstra();dijkstra1(); for (int i=1;i<=m;++i){ int x=data[i].x,y=data[i].y,z=data[i].z; if (f1[y]+f[x]+z>f[n]+k) mark[i]=1;else w[i]=f[x]+z-f[y]; }num=0;memset(dfn,0,sizeof(dfn));int flag1=0;s=0; for (int i=1;i<=n;++i) if (!dfn[i]) tarjan(i); for (int i=1;i<=s;++i) if(size[i]>=2) {flag1=1;break;} if (flag1) {printf("-1\n");continue;} memset(dp,0,sizeof(dp));memset(in,0,sizeof(in));dp[1][0]=1; for (int i=1;i<=n;++i){ for (int j=h[i];j;j=data[j].next){ if (mark[j]) continue;int y=data[j].y; for (int x=0;x+w[j]<=k;++x) in[y][x+w[j]]++; } }queue q1; for (int i=1;i<=n;++i) for (int j=0;j<=k;++j) if (!in[i][j]) q1.push(make_pair(i,j)); while(!q1.empty()){ int x=q1.front().first,kk=q1.front().second;q1.pop(); for (int i=h[x];i;i=data[i].next){ if (mark[i]) continue;int y=data[i].y; if (kk+w[i]<=k) { dp[y][kk+w[i]]+=dp[x][kk];dp[y][kk+w[i]]%=p; if (--in[y][kk+w[i]]==0) q1.push(make_pair(y,kk+w[i])); } } }int ans=0; for (int i=0;i<=k;++i) (ans+=dp[n][i])%=p; printf("%d\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。