用dijkstra做的,求调
查看原帖
用dijkstra做的,求调
1045286
z_y_w_楼主2024/5/8 18:07
#include<bits/stdc++.h>
using namespace std;
const int MAXN=205;
int n, a, b;
struct Edge
{
	int u, v, w, nxt;//链式前项星 
}edge[MAXN];
int head[MAXN], cnt;
void add(int u, int v, int w)
{
	edge[++cnt]={u, v, w, head[u]};//读入 
	head[u]=cnt;
}
struct node
{
	int a, b;
	bool operator <(const node &x) const
	{
		return x.a<a;
	}
};
priority_queue<node> q;//优先队列优化
int dis[MAXN];
bool check[MAXN];
int main()
{
	for(int i=1; i<=MAXN; i++)dis[i]=1e9+5;//初始化最大值
	cin>>n>>a>>b;
	for(int i=1; i<=n; i++){
		int c;
		cin>>c;
		if(c==0) continue;
		if(c+i<=n)
		{
			add(i, i+c, 1);
		}
		if(i-c>=1)
		{
			add(i, i-c, 1);
		}
	}
	dis[a]=0;
	q.push({0, a});
	while(q.size())
	{
		int u=q.top().b;
		q.pop();
		if(check[u]==1) continue;
		check[u]=1;
		//cout<<u<<"\n";
		for(int i=head[u]; i; i=edge[i].nxt)
		{
			int v=edge[i].v, w=edge[i].w;
			//cout<<v<<" "<<dis[v]<<" "<<w<<" ";
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({dis[v], v});
				
			}
			//cout<<dis[u]<<"\n";
			
		}
		//cout<<"\n";
	}
	if(dis[b]==1e9+5)
	{
		cout<<-1;
	}
	else
	{
		cout<<dis[b];
	}
} 

2024/5/8 18:07
加载中...