本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷[P15803 GESP202603 七级] 物流网络 - 洛谷【题目描述】一个物流网络由n nn个城市和m mm条双向公路组成。每条公路都有两个属性运输费用w i w_iwi​景观评分b i b_ibi​当一辆运输车从城市1 11运送货物到城市n nn时需要支付经过道路的运输费用之和。为了推广旅游线路物流公司推出了一项优惠政策在运输路径上可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值则只免除其中一条的费用。请你计算从城市1 11到城市n nn的最小运输费用。【输入】第一行两个整数n , m n,mn,m分别表示城市数量和公路数量。接下来m mm行每行四个整数u , v , w , b u,v,w,bu,v,w,b表示存在一条连接城市u uu和城市v vv的双向公路其中w ww为运输费用b bb为景观评分。【输出】输出一个整数表示从城市1 11到城市n nn的最小费用。如果无法到达输出-1。【输入样例】3 3 1 2 10 5 2 3 20 6 1 3 100 1【输出样例】0【算法标签】#普及# #Dijkstra#【代码详解】// 84分版本#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN5005,M5005*2;intn,m,u,v,w,b,bw,ans1e18;// ans初始化为无穷大intdist[N];// 存储到每个节点的最小距离// 边结构体structNode{intv;// 目标城市intw;// 公路运输费用intb;// 公路景观评分intbw;// 当前路径中景观评分最高的公路的运输费用};vectorNodea[N];// 邻接表存储图queueNodeq;// BFS队列// 广度优先搜索voidbfs(){memset(dist,0x3f,sizeof(dist));// 初始化距离为无穷大q.push({1,0,0,0});// 从城市1开始初始运输费用0最大景观评分0最大景观评分的公路费用0while(!q.empty()){intuq.front().v;// 当前城市intwq.front().w;// 当前累计运输费用intbq.front().b;// 当前路径中的最大景观评分intbwq.front().bw;// 当前路径中最大景观评分对应的公路运输费用q.pop();// 如果当前路径的运输费用减去最大景观评分的公路费用不小于已记录的最优值跳过if(w-bwdist[u]){continue;}dist[u]w-bw;// 更新到城市u的最优值实际需要支付的费用// 如果到达目标城市n更新全局答案if(un){ansmin(ans,w-bw);}// 遍历当前城市的所有邻接公路for(inti0;ia[u].size();i){// 如果新公路的景观评分更高或者景观评分相同但运输费用更高if(a[u][i].bb||(a[u][i].bba[u][i].wbw)){// 更新最大景观评分的公路并记录其运输费用q.push({a[u][i].v,a[u][i].ww,a[u][i].b,a[u][i].w});}else{// 否则保持原来的最大景观评分的公路q.push({a[u][i].v,a[u][i].ww,b,bw});}}}}signedmain(){cinnm;// 输入城市数量n和公路数量m// 输入每条公路的信息while(m--){cinuvwb;a[u].push_back({v,w,b});// 添加双向公路a[v].push_back({u,w,b});// 添加双向公路}bfs();// 执行BFS搜索// 输出结果if(ans1e18)// 如果没有找到路径{cout-1endl;}else{coutansendl;// 输出最小运输费用}return0;}// AC版本#includebits/stdc.husingnamespacestd;#defineintlonglongtypedefpairint,intPII;// 优先队列元素类型(距离, 城市)constintN5005;// 公路结构体structNode{intu,v,w,b;// 连接的两个城市u,v运输费用w景观评分b}e[5005];// 存储所有公路intn,m,u,v,w,idx,d;// 输入变量idx: 公路编号d: 临时距离intdist[N];// 最短距离数组存储从城市1到各城市的最小距离intans1e18;// 最终答案初始化为无穷大vectorPIIa[N];// 邻接表存储(目标城市, 公路编号)priority_queuePII,vectorPII,greaterPIIpq;// 小顶堆优先队列用于Dijkstra// 排序比较函数先按景观评分b升序评分相同则按运输费用w升序boolcmp(Node x,Node y){if(x.by.b)// 如果景观评分相同{returnx.wy.w;// 运输费用小的排在前面}returnx.by.b;// 景观评分小的排在前面}// Dijkstra算法x表示当前尝试免去费用的公路编号voiddijkstra(intx){memset(dist,0x3f,sizeof(dist));// 初始化所有距离为无穷大pq.push({0,1});// 起点城市1距离为0while(!pq.empty()){intupq.top().second;// 当前城市intdpq.top().first;// 当前距离pq.pop();// 剪枝如果当前距离不小于已记录的最短距离或者不小于当前全局最优解if(ddist[u]||dans){continue;}dist[u]d;// 更新最短距离// 如果到达目标城市nif(un){ansmin(ans,d);// 更新全局最优解break;// 找到一条到n的路径就可以提前结束}// 遍历当前城市的所有邻接边for(inti0;ia[u].size();i){intva[u][i].first;// 邻接城市intidxa[u][i].second;// 公路编号if(idxx)// 如果这条公路是当前尝试免去费用的{pq.push({d,v});// 经过这条公路不增加费用}else{pq.push({de[idx].w,v});// 正常增加运输费用}}}}signedmain(){cinnm;// 输入城市数量和公路数量// 输入所有公路信息for(inti1;im;i){cine[i].ue[i].ve[i].we[i].b;}// 将公路按景观评分升序排序评分相同则按费用升序sort(e1,em1,cmp);// 构建邻接表for(inti1;im;i){a[e[i].u].push_back({e[i].v,i});// 双向公路a[e[i].v].push_back({e[i].u,i});// 双向公路}// 从评分最高的公路开始倒序枚举for(intim;i1;i--){// 尝试免去第i条公路当前剩余公路中景观评分最高的dijkstra(i);// 移除这条公路为下一轮准备a[e[i].u].pop_back();a[e[i].v].pop_back();}// 输出结果if(ans1e18)// 如果没有找到从1到n的路径{cout-1endl;}else{coutansendl;// 输出最小运输费用}return0;}【运行结果】3 3 1 2 10 5 2 3 20 6 1 3 100 1 0