题解【CodeForces 910A The Way to Home】

题目大意

一只青蛙现在在一个数轴上，它现在要从点 \(1\) 跳到点 \(n\) ，它每次可以向右跳不超过 \(d\) 个单位。比如，它可以从点 \(x\) 跳到点 \(x+a\)（\(1\le a\le d\)）。

特别的，青蛙只能在有百合花的点上停留。保证点 \(1\) 和点 \(n\) 之间有一些点有百合花，并且起点和终点有百合花。请输出青蛙到达点 \(n\) 的最小跳跃次数。

题解

注意到 \(n\le 100\)，暴力将 \(x\to x+a\) 建图跑最短路即可。

#include<iostream>

#include<ctime>

#include<queue>

#include<stack>

#include<cmath>

#include<iterator>

#include<cctype>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=2001,INF=0x3f3f3f3f;

typedef long long ll;

typedef vector<pair<int,ll> > graph[N];

graph g;

inline void addedge(int u,int v,ll w){g[u].push_back(make_pair(v,w));}

int n,d,dis[N];

bool vis[N];

string str;

struct node

{

	int idx,dis;

	node(int _idx,int _dis){idx=_idx; dis=_dis;}

	inline bool operator<(const node& w)const{return dis>w.dis;}

};

inline void dij(int s)

{

	memset(dis,0x3f,sizeof dis);

	priority_queue<node> q; q.push(node(s,0)); dis[s]=0;

	while (!q.empty())

	{

		node now=q.top(); q.pop(); int nowi=now.idx,S=g[nowi].size();

		if (vis[nowi]) continue; vis[nowi]=true;

		for (int i=0;i<S;i++)

		{

			int v=g[nowi][i].first,w=g[nowi][i].second;

			if (dis[nowi]+w<dis[v]){dis[v]=dis[nowi]+w; if (!vis[v]) q.push(node(v,dis[v]));}

		}

	}

}

int main()

{

	scanf("%d%d",&n,&d); cin>>str;

	for (int i=0;i<n;i++)

		if (str[i]-'0')

			for (int j=1;j<=d;j++)

			{

				int pos=i+j; if ((pos>n)||(pos==i)||(str[pos]=='0')) continue;

				addedge(i+1,pos+1,1);

			}

	dij(1); printf("%d",(dis[n]==INF)?-1:dis[n]);

	return 0;

}

巴特西

题解【CodeForces 910A The Way to Home】

题目大意

题解

最新文章

热门文章