欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客
P1673 Part Acquisition
【题目来源】
洛谷：[P1673 USACO05FEB] Part Acquisition S - 洛谷
【题目描述】
奶牛们接到了寻找一种新型挤奶机的任务，为此它们准备依次经过N ( 1 ≤ N ≤ 5 × 10 4 ) N(1\le N\le 5\times 10^4)N(1≤N≤5×104)颗行星，在行星上进行交易。为了方便，奶牛们已经给可能出现的K ( 1 ≤ K ≤ 10 3 ) K(1\le K\le 10^3)K(1≤K≤103)种货物进行了由1 11到K KK的标号。由于这些行星都不是十分发达。没有流通的货币，所以在每个市场里都只能用固定的一种货物去换取另一种货物。奶牛们带着一种上好的饲料从地球出发，希望在使用的物品的种类数量最少的情况下，最终得到所需要的机器。饲料的标号为1 11，所需要的机器的标号为K KK。如果任务无法完成，输出− 1 -1−1。
【输入】
第1 11行是两个数字N NN和K KK。
第2 22到N + 1 N+1N+1行，每行是两个数字A i A_iAi和B i B_iBi，表示第i ii颗行星为得到A i A_iAi愿意提供B i B_iBi。
【输出】
输出最少经手物品数。
【输入样例】
6 5 1 3 3 2 2 3 3 1 2 5 5 4【输出样例】
4【解题思路】
【算法标签】
《洛谷 P1673 Part Acquisition》 #最短路# #USACO# #2005#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;// 定义常量constintN=50005;// 最大节点数constintM=N*2;// 最大边数，无向图需要乘以2intn;// 节点总数intk;// 目标节点inth[N];// 邻接表头数组inte[M];// 边数组，存储边的终点intne[M];// 邻接表next数组intidx;// 边的索引计数器intdist[N];// 距离数组，存储从节点1到各节点的最短距离// 添加边的函数voidadd(inta,intb){e[idx]=b;// 设置边的终点ne[idx]=h[a];// 新边指向原链表的头h[a]=idx++;// 更新链表头，并递增索引}// 广度优先搜索函数，从节点1开始搜索voidbfs(){queue<int>q;// 创建队列用于BFSq.push(1);// 从节点1开始搜索// 初始化距离数组，将所有距离设为无穷大for(inti=1;i<=n;i++){dist[i]=1e9;// 1e9表示无穷大}dist[1]=1;// 节点1到自身的距离为1（这里从1开始计数，不是0）// BFS主循环while(!q.empty()){intt=q.front();// 取出队首节点q.pop();// 弹出队首节点// 遍历节点t的所有邻居for(inti=h[t];i!=-1;i=ne[i]){intj=e[i];// 邻居节点// 如果找到更短的路径if(dist[j]>dist[t]+1){dist[j]=dist[t]+1;// 更新距离q.push(j);// 将邻居节点加入队列}}}}intmain(){// 初始化邻接表头数组memset(h,-1,sizeof(h));// 读入节点数和目标节点cin>>n>>k;// 读入n-1条边（因为树有n-1条边）for(inti=1;i<=n;i++){intu,v;cin>>u>>v;add(u,v);// 添加边u->v// 注意：这里似乎缺少了add(v, u)，应该是无向图的输入}// 执行BFS搜索bfs();// 输出结果if(dist[k]==1e9)// 如果目标节点不可达{cout<<-1<<endl;}else// 如果可达{cout<<dist[k]<<endl;}return0;}【运行结果】
6 5 1 3 3 2 2 3 3 1 2 5 5 4 4
