洛谷题解-P1673 [USACO05FEB] Part Acquisition S

https://www.luogu.com.cn/problem/P1673

题目描述

奶牛们接到了寻找一种新型挤奶机的任务，为此它们准备依次经过 N(1≤N≤5×104)N(1\le N\le 5\times 10^4)N(1≤N≤5×104) 颗行星，在行星上进行交易。为了方便，奶牛们已经给可能出现的 K(1≤K≤103)K(1\le K\le 10^3)K(1≤K≤103) 种货物进行了由 111 到 KKK 的标号。由于这些行星都不是十分发达。没有流通的货币，所以在每个市场里都只能用固定的一种货物去换取另一种货物。奶牛们带着一种上好的饲料从地球出发，希望在使用的物品的种类数量最少的情况下，最终得到所需要的机器。饲料的标号为 111，所需要的机器的标号为 KKK。如果任务无法完成，输出 −1-1−1。

输入格式

第 111 行是两个数字 NNN 和 KKK。

第 222 到 N+1N+1N+1 行，每行是两个数字 AiA_iAi​ 和 BiB_iBi​，表示第 iii 颗行星为得到 BiB_iBi​ 愿意提供 AiA_iAi​。

输出格式

输出最少经手物品数。

输入输出样例

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

4

说明/提示

奶牛们至少需要 444 种不同标号的物品，先用 111 去交换 333，再用 333 去交换 222，最后用 222 交换得到 555。

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

1.边权为1的话也可以用dijk..算法求最短路  ；  2.读题结合样例理解（不要弄混了走不出来）    详解见下

很简单的板子题，主要在于读题和分析

第 i 颗行星为得到 Bi 愿意提供 Ai​  的意思是

拿Ai换Bi（提供Ai是你需要给他Ai，得到Bi是你得到Bi），在这里我分析了很久，导致被误导，一定不要弄混题意了走不出来了！！！多思考分析一下

#include <bits/stdc++.h>
using namespace std;

const int N=5e4+5;
struct node
{
	int v, w;
	bool operator <(const node &A) const
	{
		return w>A.w;
	}
};
int n, k, u1, v1, dis[N], vis[N];
vector<node> a[N];
priority_queue<node> q;
void dij(int s)
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s]=0, q.push({s, 0});
	
	while (!q.empty())
	{
		int u=q.top().v;
		q.pop();
		
		if (vis[u]) continue;
		vis[u]=1;
		
		for (int i=0; i<a[u].size(); i++)
		{
			int v=a[u][i].v, w=a[u][i].w;
			if (!vis[v] && dis[v]>dis[u]+w) 
			{
				dis[v]=dis[u]+w;
				q.push({v, dis[v]});
			}
		}
	}
}
int main()
{
	scanf("%d%d", &n, &k);
	for (int i=1; i<=n; i++)
	{
		scanf("%d%d", &u1, &v1);
		a[u1].push_back({v1, 1}); //边权为1照样写，不用写 push(v)
	}
	dij(1);
	
	if (dis[k]==dis[0]) printf("-1"); //是k，结合题意
	else printf("%d", dis[k]+1);
	return 0;
}