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 N1N1行每行是两个数字A i A_iAi​和B i B_iBi​表示第i ii颗行星为得到A i A_iAi​愿意提供B i B_iBi​。输出格式输出最少经手物品数。输入输出样例 #1输入 #16 5 1 3 3 2 2 3 3 1 2 5 5 4输出 #14说明/提示奶牛们至少需要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×1041 ≤ K ≤ 10 3 1\le K\le 10^31≤K≤103。解题思路本题是图论最短路的经典问题。将每种货物视为图中的一个节点每次交易规则“用 A 换 B”视为一条从 A 到 B 的有向边。奶牛初始拥有 1 号货物目标为 K 号货物要求经过的货物种类数最少。这等价于求从 1 号节点到 K 号节点的最短路径长度以节点数计其中每条边的权值为 1。1. 问题等价转化有 K 种货物编号 1~KN 条交易规则。对于每条规则(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 ≤ 1000N ≤ 5×10⁴完全可行。空间复杂度邻接矩阵 O(K²) 存储边关系距离数组 O(K)。总结将货物交换建模为有向图最短路问题边权为 1以起点物品数作为初始距离使用 Dijkstra 求出从 1 到 K 的最少物品种类数。该方法简洁高效适合小规模节点数K ≤ 1000的图。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll MAXN10005;constll INF1e18;constll M1e610;constll mod1e97;ll n,k;ll dis[MAXN];boolf[MAXN][MAXN],vis[MAXN];voiddij(ll st){fill(dis,disMAXN,INF);memset(vis,false,sizeof(vis));dis[st]1;while(1){ll u-1;for(ll i1;ik;i)if(!vis[i](u-1||dis[i]dis[u]))ui;if(u-1)break;vis[u]true;for(ll i1;ik;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 i1,u,v;in;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;}