P1673 Part Acquisition S【洛谷算法习题】-二趣网

P1673 Part Acquisition S

网页链接

P1673 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。

输出格式

输出最少经手物品数。

输入输出样例 #1

输入 #1

6 5 1 3 3 2 2 3 3 1 2 5 5 4

输出 #1

说明/提示

奶牛们至少需要4 44种不同标号的物品，先用1 11去交换3 33，再用3 33去交换2 22，最后用2 22交换得到5 55。

1 ≤ N ≤ 5 × 10 4 1\le N\le 5\times 10^41≤N≤5×104，1 ≤ K ≤ 10 3 1\le K\le 10^31≤K≤103。

解题思路

本题是图论最短路的经典问题。将每种货物视为图中的一个节点，每次交易规则“用 A 换 B”视为一条从 A 到 B 的有向边。奶牛初始拥有 1 号货物，目标为 K 号货物，要求经过的货物种类数最少。这等价于求从 1 号节点到 K 号节点的最短路径长度（以节点数计），其中每条边的权值为 1。

1. 问题等价转化

有 K 种货物（编号 1~K），N 条交易规则。
对于每条规则(A, B)，表示可以用货物 A 换取货物 B，即存在一条从 A 到 B 的有向边。
起点为 1，终点为 K。每次交换增加一种经手的货物。
目标是最小化经过的货物种类数，也就是求从 1 到 K 的最短路径的节点数。如果不可达，输出-1。

2. 算法实现：朴素 Dijkstra

由于边权均为 1，可以用 BFS 求解；但这里使用朴素 Dijkstra，因为 K ≤ 1000，邻接矩阵可以承受 O(K²) 的复杂度。

建图：使用二维布尔数组f[u][v]表示是否存在从 u 到 v 的有向边。
初始化距离：
- dis[1] = 1（起点本身算一种物品）。
- 其余节点距离设为INF。
Dijkstra 过程：
- 每次从未访问节点中选出距离最小的节点 u。
- 标记 u 已访问。
- 对于所有未访问的邻接点 v，更新dis[v] = min(dis[v], dis[u] + 1)。
输出答案：
- 若dis[K]仍为INF，输出-1；
- 否则输出dis[K]，即最少经手物品数。

3. 复杂度分析

时间复杂度：建图 O(N)，Dijkstra 双重循环 O(K²)，总复杂度 O(K² + N)。K ≤ 1000，N ≤ 5×10⁴，完全可行。
空间复杂度：邻接矩阵 O(K²) 存储边关系，距离数组 O(K)。

总结

将货物交换建模为有向图最短路问题，边权为 1，以起点物品数作为初始距离，使用 Dijkstra 求出从 1 到 K 的最少物品种类数。该方法简洁高效，适合小规模节点数（K ≤ 1000）的图。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll MAXN=10005;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,k;ll dis[MAXN];boolf[MAXN][MAXN],vis[MAXN];voiddij(ll st){fill(dis,dis+MAXN,INF);memset(vis,false,sizeof(vis));dis[st]=1;while(1){ll u=-1;for(ll i=1;i<=k;i++)if(!vis[i]&&(u==-1||dis[i]<dis[u]))u=i;if(u==-1)break;vis[u]=true;for(ll i=1;i<=k;i++)if(!vis[i]&&f[u][i])dis[i]=min(dis[i],dis[u]+1);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(f,false,sizeof(f));scanf("%lld%lld",&n,&k);for(ll i=1,u,v;i<=n;i++){scanf("%lld%lld",&u,&v);f[u][v]=true;}dij(1);if(dis[k]==INF)printf("-1\n");elseprintf("%lld\n",dis[k]);return0;}

企业官网建设流程全解析