请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

【洛谷】P1673 [USACO05FEB] Part Acquisition S

2023-07-13

1:题题简化:一共有k个物品,最开始有物品1,问最少经过几次交换可以换到k物品。

(转化-->k个点,n条有向边,权值都为1,求1点到k点的最短路)

权值为1:我们把为k个物品当成点,星球之间穿梭看成当前两个物品可以交换,求交换到k物品的最小交换次数,那权值为1的含义就交换了一次物品。

注意结果要+1因为我们求出来的是最小交换次数(默认1物品是拥有的),但是题目是要求输出一共的商品种类(即加上1物品)

注意:是有向边。

okk,那经过上方激烈分析(狗头),这题就变成最短路模板啦~

上ACcode:(dijkstra)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define inf 0x3f3f3f3f
typedef pair<int,int>PII;
const int N=1e3+10,M=2*5e4+10;
struct E{
	int to,w,next;
}e[M];
int head[N],cnt,dis[N],n,m,u,v;
bool vis[N];
void add(int u,int v,int w){
	e[++cnt]={v,w,head[u]},head[u]=cnt;
} 
void dijkstra(){//模板 
	for(int i=1;i<=n;i++) dis[i]=inf;
	dis[1]=0;
	priority_queue<PII,vector<PII>,greater<PII>>q;
	q.push({0,1});
	while(!q.empty()){
		int t=q.top().second;
		q.pop();
		if(vis[t]) continue;
		vis[t]=true;
		for(int i=head[t];i;i=e[i].next){
			int j=e[i].to;
			if(dis[j]>dis[t]+e[i].w){
				dis[j]=dis[t]+e[i].w;
				q.push({dis[j],j});
			}
		} 
	}
}
void solve(){
     cin>>m>>n;
     for(int i=1;i<=m;i++){
     	cin>>u>>v;
     	add(u,v,1);//代表u与v可以交换 
	 }
	 dijkstra();//模板 
	 if(dis[n]>=inf) cout<<"-1\n";
	 else cout<<dis[n]+1<<"\n";//+1:本身在一点也算一件物品 
}
signed main(){
	
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
	return 0;
} 

over~

相关阅读

手机版|MSIPO技术圈 皖ICP备19022944号-2

Copyright © 2024, msipo.com

返回顶部