本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P3953 [NOIP 2017 提高组] 逛公园 - 洛谷
【题目描述】
策策同学特别喜欢逛公园。公园可以看成一张N NN个点M MM条边构成的有向图，且没有 自环和重边。其中1 11号点是公园的入口，N NN号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从1 11号点进去，从N NN号点出来。
策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果1 11号点到N NN号点的最短路长为d dd，那么策策只会喜欢长度不超过d + K d + Kd+K的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对P PP取模。
如果有无穷多条合法的路线，请输出− 1 -1−1。
【输入】
第一行包含一个整数T TT, 代表数据组数。
接下来T TT组数据，对于每组数据： 第一行包含四个整数N , M , K , P N,M,K,PN,M,K,P，每两个整数之间用一个空格隔开。
接下来M MM行，每行三个整数a i , b i , c i a_i,b_i,c_iai,bi,ci，代表编号为a i , b i a_i,b_iai,bi的点之间有一条权值为c i c_ici的有向边，每两个整数之间用一个空格隔开。
【输出】
输出文件包含T TT行，每行一个整数代表答案。
【输入样例】
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【算法标签】
#提高+# #记忆化搜索#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=100005,M=2*200005,K=55,INF=1e18;typedefpair<int,int>PII;// 存储(距离, 节点)的对intt,n,m,k,p;// t: 测试用例数, n: 节点数, m: 边数, k: 最大额外距离, p: 模数vector<PII>g[N];// 正向图vector<PII>g2[N];// 反向图intdist[N];// 从起点1到各点的最短距离boolst[N];// Dijkstra算法中的访问标记priority_queue<PII,vector<PII>,greater<PII>>heap;// 小根堆，用于Dijkstraintf[N][K];// 记忆化搜索数组boolvis[N][K],in[N][K];// 访问标记和递归栈标记boolflag;// 标志位，用于检测无穷多条路径// Dijkstra算法，计算从起点s到所有点的最短距离voiddijkstra(ints){memset(dist,0x3f,sizeof(dist));// 初始化距离为无穷大memset(st,false,sizeof(st));// 初始化访问标记dist[s]=0;// 源点距离为0heap.push({0,s});// 将起点加入堆，first存储距离，second存储节点编号while(!heap.empty()){autond=heap.top();// 取出距离最小的节点heap.pop();intveid=nd.second;// 当前节点编号intdistance=nd.first;// 当前距离if(st[veid]==true)// 如果已经处理过，跳过{continue;}st[veid]=true;// 标记为已处理// 遍历当前节点的所有邻接边for(inti=0;i<g[veid].size();i++){autondi=g[veid][i];intj=ndi.second;// 邻接节点intdistance=ndi.first;// 边权// 松弛操作if(dist[j]>dist[veid]+distance){dist[j]=dist[veid]+distance;// 更新最短距离heap.push({dist[j],j});// 将更新后的节点加入堆}}}}// 记忆化搜索函数，计算从节点u出发，实际距离为dd的路径数intdfs(intu,intdd){intex=dd-dist[u];// 额外距离 = 实际距离 - 最短距离// 边界条件检查if(ex<0||ex>k)// 额外距离超出范围{return0;}// 检测环：如果当前状态已经在递归栈中，说明存在环if(in[u][ex]){flag=true;// 设置标志位，表示存在无穷多条路径return0;}// 如果已经计算过，直接返回结果if(f[u][ex]!=-1){returnf[u][ex];}in[u][ex]=true;// 标记当前状态在递归栈中intres=0;// 初始化结果// 遍历反向图中的邻接边（从u向前的边）for(autoe:g2[u]){intv=e.second;// 前驱节点intw=e.first;// 边权// 递归计算从前驱节点v到终点的路径数res=(res+dfs(v,dd-w))%p;// 如果检测到环，直接返回if(flag){in[u][ex]=false;// 清除递归栈标记return0;}}in[u][ex]=false;// 清除递归栈标记// 如果当前节点是起点1且额外距离为0，表示找到一条合法路径if(u==1&&ex==0){res=1;}returnf[u][ex]=res;// 记忆化并返回结果}signedmain(){cin>>t;// 输入测试用例数while(t--){cin>>n>>m>>k>>p;// 输入节点数、边数、最大额外距离、模数flag=false;// 重置标志位// 清空图和反向图for(inti=1;i<=n;i++){g[i].clear();g2[i].clear();}// 初始化记忆化数组和标记数组memset(f,-1,sizeof(f));memset(in,false,sizeof(in));// 输入边信息for(inti=1;i<=m;i++){intu,v,w;cin>>u>>v>>w;g[u].push_back({w,v});// 正向图g2[v].push_back({w,u});// 反向图}// 从起点1运行Dijkstra算法，计算最短距离dijkstra(1);intans=0;// 初始化答案// 计算额外距离从0到k的所有可能路径数for(inti=0;i<=k;i++){ans=(ans+dfs(n,dist[n]+i))%p;}// 如果检测到环（无穷多条路径），输出-1if(flag){cout<<-1<<endl;}else{cout<<ans<<endl;}}return0;// 程序正常结束}【运行结果】
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 3 2 2 0 10 1 2 0 2 1 0 -1
