本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P10110 [GESP202312 七级] 商品交易 - 洛谷【题目描述】市场上共有N NN种商品编号从0 00至N − 1 N-1N−1其中第i ii种商品价值v i v_ivi​元。现在共有M MM个商人编号从0 00至M − 1 M-1M−1。在第j jj个商人这你可以使用你手上的第x j x_jxj​种商品交换商人手上的第y j y_jyj​种商品。每个商人都会按照商品价值进行交易具体来说如果v x j v y j v_{x_j}v_{y_j}vxj​​vyj​​他将会付给你v x j − v y j v_{x_j}-v_{y_j}vxj​​−vyj​​元钱否则那么你需要付给商人v y j − v x j v_{y_j}-v_{x_j}vyj​​−vxj​​元钱。除此之外每次交易商人还会收取1 11元作为手续费不论交易商品的价值孰高孰低。你现在拥有商品a aa并希望通过一些交换来获得商品b bb。请问你至少要花费多少钱当然这个最小花费也可能是负数这表示你可以在完成目标的同时赚取一些钱。【输入】第一行四个整数N , M , a , b N , M , a , bN,M,a,b分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证0 ≤ a , b N 0 \le a,b N0≤a,bN保证a ≠ b a \ne bab。第二行N NN个用单个空格隔开的正整数v 0 , v 1 , … , v N − 1 v_0,v_1,…,v_{N-1}v0​,v1​,…,vN−1​依次表示每种商品的价值。保证1 ≤ v i ≤ 10 9 1≤v_i≤10^91≤vi​≤109。接下来M MM行每行两个整数x j , y j x_j,y_jxj​,yj​表示在第j jj个商人这你可以使用第x j x_jxj​种商品交换第y j y_jyj​种商品。保证0 ≤ x j , y j N 0≤x_j,y_jN0≤xj​,yj​N保证x j ≠ y j x_j≠y_jxj​yj​。【输出】输出一行一个整数表示最少的花费。特别地如果无法通过交换换取商品b bb请输出No solution。【输入样例】3 5 0 2 1 2 4 1 0 2 0 0 1 2 1 1 2【输出样例】5【算法标签】#普及 #SPFA【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 最大节点数constintMN*2;// 最大边数无向图×2intn,m,a,b;// n: 节点数, m: 边数, a: 起点, b: 终点intv[N];// 每个节点的值inth[N],e[M],ne[M],w[M],idx;// 邻接表intdist[N];// 最短距离boolst[N];// 节点是否在队列中// 添加有向边voidadd(inta,intb,intc){e[idx]b;// 边的终点w[idx]c;// 边的权重ne[idx]h[a];// 指向a的下一条边h[a]idx;// 更新a的第一条边}// SPFA算法求最短路voidspfa(){// 初始化距离为无穷大memset(dist,0x3f,sizeof(dist));dist[a]0;// 起点距离为0queueintq;// SPFA队列q.push(a);// 起点入队st[a]true;// 标记起点在队列中while(!q.empty()){inttq.front();// 取出队首节点q.pop();// cout t t endl; // 调试输出st[t]false;// 标记t不在队列中// 遍历t的所有邻接边for(intih[t];i!-1;ine[i]){intje[i];// 邻接节点// 松弛操作if(dist[j]dist[t]w[i]){dist[j]dist[t]w[i]1;// 更新距离if(!st[j])// 如果j不在队列中{q.push(j);// j入队st[j]true;// 标记j在队列中}}}}// 调试输出距离数组// for (int i0; in; i)// cout dist[i] ;// cout endl;}intmain(){// 初始化邻接表memset(h,-1,sizeof(h));// 输入节点数、边数、起点、终点cinnmab;// 输入每个节点的值for(inti0;in;i){cinv[i];}// 输入边并建图while(m--){intx,y;cinxy;// 添加有向边权重为v[y] - v[x]add(x,y,v[y]-v[x]);}// 运行SPFA算法spfa();// 输出结果if(dist[b]0x3f3f3f3f)// 如果终点不可达{puts(No solution);}else{coutdist[b]endl;// 输出最短距离}return0;}【运行结果】3 5 0 2 1 2 4 1 0 2 0 0 1 2 1 1 2 5