您现在的位置是:首页 > 正文

【NOIP2017Day1T3】【洛谷P3953】逛公园

2024-01-30 23:15:02阅读 1

问题描述

策策同学特别喜欢逛公园。公园可以看成一张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行,每行一个整数代表答案。

样例输入

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

样例输出

3
-1

样例解释

数据范围

题解

先用SPFA求单源最短路(Dijkstra优先队列优化会T掉一个点不知道为什么)

f[u][k]表示从u到n长度不超过mindis(u,n)+K-k的方案数

f[u][k]=Σ f[v][k+d[u]-d[v]+w[u][v]]

d[u]表示1到u的最短路,w[u][v]表示从u指向v的边的权值,d[u]-d[v]+w[u][v]表示  从u经过v到n的路径  比   从u走最短路到n的路径  多走的值

当且仅当存在0环时,有无穷多条合法路线,记忆化搜素转移状态时,vis[u][k]表示当前f[u][k]这个状态是否在栈里,如果转移f[u][k]时f[u][k]已经在栈里了,说明存在0环,直接输出-1

 

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <queue>
 5 #define pa pair<int,int>
 6 using namespace std;
 7 const int maxn=100005;
 8 struct node{
 9     int u,w,nex;
10 }g[400005];
11 int n,m,T,K,P,fir[100005],d[100005],num,f[100005][60];
12 bool vis[100005][60],mak[100005];
13 int q[100010],h,t;
14 void add(int x,int y,int z) 
15 {
16     g[++num].u=y;  g[num].w=z;  g[num].nex=fir[x];  fir[x]=num;
17     return;
18 }
19 void spfa() 
20 {
21     int u,v,i;
22     h=0;  t=1;  q[1]=1;  mak[1]=1;
23     while (h!=t) 
24     {
25         u=q[(++h)%=maxn];
26         mak[u]=0;
27         for (i=fir[u];i;i=g[i].nex) 
28         {
29             v=g[i].u;
30             if (d[u]+g[i].w<d[v]) 
31             {
32                 d[v]=d[u]+g[i].w;
33                 if (mak[v]) continue;
34                 q[(++t)%=maxn]=v;
35                 mak[v]=1;
36             }
37         }
38     }
39     return;
40 }
41 int dp(int u,int k) 
42 {
43     if (k>K) return 0;
44     if (vis[u][k]) return -1;
45     if (f[u][k]!=-1) return f[u][k];
46     vis[u][k]=1;
47     int i,j,v,s;
48     f[u][k]=(u==n);
49     for (i=fir[u];i;i=g[i].nex) 
50     {
51         v=g[i].u;
52         s=dp(v,k+(d[u]-d[v]+g[i].w));
53         if (s!=-1) f[u][k]=(f[u][k]+s)%P;
54         else return -1;
55     }
56     vis[u][k]=0;
57     return f[u][k];
58 }
59 int main() 
60 {
61     int i,j,k,x,y,z;
62     scanf("%d",&T);
63     while (T--) 
64     {
65         memset(mak,0,sizeof(mak));
66         memset(vis,0,sizeof(vis));
67         memset(fir,0,sizeof(fir));
68         memset(d,63,sizeof(d));
69         memset(f,-1,sizeof(f));
70         scanf("%d%d%d%d",&n,&m,&K,&P);
71         d[1]=num=0;
72         memset(vis,0,sizeof(vis));
73         for (i=1;i<=m;i++)
74           scanf("%d%d%d",&x,&y,&z),
75           add(x,y,z);
76         spfa();
77         printf("%d\n",dp(1,0));
78     }
79     return 0;
80 }

 

转载于:https://www.cnblogs.com/rabbit1103/p/9812589.html

网站文章

  • 远程计算机 无用户名,远程桌面登陆没有成功,但是用户名密码正确

    远程计算机 无用户名,远程桌面登陆没有成功,但是用户名密码正确

    1.第一种情况:安全策略问题开始-->运行->gpedit.msc->计算机配置->Windows设置->安全设置->本地策略->安全选项->网络访问:本地帐户的共享和安全模型。 修改为使用经典模式2.第二种情况:用户所在域问题7 Win8以后的Microsoft账户问题由于Win8以后开始使用MS账户,由此产生了一些“无法远程”的问题。究其原因,是...

    2024-01-30 23:14:54
  • 快速容易地处理Windows、Mac 和Linux系统中文件路径问题

    快速容易地处理Windows、Mac 和Linux系统中文件路径问题

    作者:景略集智 链接:https://www.zhihu.com/question/48755767/answer/423475686 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 今天分享一个Python 3里的技巧:快速容易地处理Windows、Mac 和Linux系统中文件路径问题。 编程中有个比较烦人的事情,Windows系统在文件名中间用的是反...

    2024-01-30 23:14:26
  • 【解题笔记】leetcode寻找两个正序数组的中位数

    【解题笔记】leetcode寻找两个正序数组的中位数

    文章目录问题转化解题步骤第一个条件:第二个条件:根据上述两个条件编码:极端情况:得到中位数注意完整代码 问题转化 首先,考虑只有一个有序数组的情况:寻找中位数的问题可以转化为寻找一条分割线,满足以下两...

    2024-01-30 23:14:11
  • 记chrome打不开网址,无法搜索问题

    下载插件,解压后拖入chrome的扩展程序中,可以打开国内网址。

    2024-01-30 23:14:04
  • PHP不用临时变量, 怎么交换两个整数变量的值. 譬如$a=2 $b=3使用第三个变量交换他们的值

    如果能用第三个变量那么问题就很简单了$a=2; $b=3; $c=$a; $b=$a; $a=$c;搞定现在不允许有$c, 那可咋整呢方案一 用数组$a=2;$b=3;$a=[$a, $b];$b=...

    2024-01-30 23:13:35
  • CSS属性总结(三):positioning, dimension, list, table

    CSS属性总结(三):positioning, dimension, list, table

    定位 position 设置元素的定位类型,相当于声明当前元素的布局所使用的定位机制,需要left、top、right、bottom、z-index等属性配合使用,否则没有实际效果。取值如下表所示: top、bottom、left、right 设置元素的上/下/左/右外边距的边缘与包含该元素的上/下/左/右边界之间的偏移。取值可以是auto,表示浏览器自动计算距离;也可以是带单位的...

    2024-01-30 23:13:27
  • Flink读取HDFS上的Parquet文件生成DataSet

    首先打开Flink的官方网站,查看一下DataSet已支持的数据源。 File-based readTextFile(path) / TextInputFormat - Reads files line wise and returns them as Strings. readTextFileWithValue(path) / TextValueInputFormat - Reads fi...

    2024-01-30 23:13:21
  • Python 文件操作

    python中对文件、文件夹(文件操作函数)的操作需要涉及到os模块和shutil模块。得到当前工作目录,即当前Python脚本工作的目录路径: os.getcwd()返回指定目录下的所有文件和目录名:os.listdir()函数用来删除一个文件:os.remove()删除多个目录:os.removedirs(r“c:\python”)检验给出的

    2024-01-30 23:13:15
  • Python代码编写规范

    Python代码编写规范

    Python代码编写规范

    2024-01-30 23:12:47
  • Java开发琐碎语法(长期更新)

    1、List赋初值可使用:Arrays.asList(0.1, 0.25, 0.5, 0.75, 0.9);3、BigDecimal的加减乘除:add、subtract、multiply、divide...

    2024-01-30 23:12:42