当前位置：首页 > news >正文

题解：洛谷 P10110 [GESP202312 七级] 商品交易

news 2026/5/11 11:33:53

本文分享的必刷题目是从蓝桥云课、洛谷、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,b<N，保证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_j<N0≤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

【输出样例】

【算法标签】

#普及 #SPFA

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 最大节点数constintM=N*2;// 最大边数（无向图×2）intn,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;// 起点距离为0queue<int>q;// SPFA队列q.push(a);// 起点入队st[a]=true;// 标记起点在队列中while(!q.empty()){intt=q.front();// 取出队首节点q.pop();// cout << "t " << t << endl; // 调试输出st[t]=false;// 标记t不在队列中// 遍历t的所有邻接边for(inti=h[t];i!=-1;i=ne[i]){intj=e[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 i=0; i<n; i++)// cout << dist[i] << " ";// cout << endl;}intmain(){// 初始化邻接表memset(h,-1,sizeof(h));// 输入节点数、边数、起点、终点cin>>n>>m>>a>>b;// 输入每个节点的值for(inti=0;i<n;i++){cin>>v[i];}// 输入边并建图while(m--){intx,y;cin>>x>>y;// 添加有向边，权重为v[y] - v[x]add(x,y,v[y]-v[x]);}// 运行SPFA算法spfa();// 输出结果if(dist[b]==0x3f3f3f3f)// 如果终点不可达{puts("No solution");}else{cout<<dist[b]<<endl;// 输出最短距离}return0;}