专栏首页wymCF910A The Way to Home SPFA(队列优化)

CF910A The Way to Home SPFA(队列优化)

题意翻译

题目描述

一只青蛙现在在一个数轴上,它现在要从点 111 跳到点 nnn ,它每次可以向右跳不超过 ddd 个单位。比如,它可以从点 xxx 跳到点 x+ax+ax+a (1<=a<=d)( 1<=a<=d )(1<=a<=d) 。特别的,青蛙只能在有百合花的点上停留。保证点 111 和点 nnn 之间有一些点有百合花。请输出青蛙到达点 nnn 的最小跳跃次数。

输入输出格式

输入格式

输入的第一行包括两个正整数 nnn 和 ddd (2<=n<=100,1<=d<=n−1)( 2<=n<=100, 1<=d<=n-1 )(2<=n<=100,1<=d<=n−1) 。 输入的第二行是一个长度为 nnn 的无空格字符串,由01组成,表示哪些点上有百合花(1表示有)。保证点 111 和点 nnn 有百合花。

输出格式

输出青蛙的最小跳跃次数。如果它不可能到达,输出-1。

输入

8 4

10010101

输出

2

说明

在样例1中,青蛙可以从点 111 跳3个单位到点 444 ,再从点 444 跳4个单位到点 888 . 在样例2中,青蛙不能到达点 nnn ,因为它至少需要跳3个单位,但它最多只能跳2个单位。

其实是贪心,熟悉一下spfa

//spfa 队列优化 
#include <bits/stdc++.h>
using namespace std;
int dis[105];
int head[105],cnt;
int vis[105],a[105];
int n,d;
const int INF = 9999999;
struct Edge{
	int v,nxt;
};
Edge edge[1005];
void add(int u,int v){
	cnt++;
	edge[cnt].v = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}
void spfa(){
	for(int i=0;i<=n;i++)dis[i] = INF;
	queue<int> q;
	dis[1] = 0; vis[1] = 1; q.push(1);
	while(!q.empty()){
		int u = q.front(); q.pop(); vis[u] = 0;
		for(int v,w,i=head[u];i;i=edge[i].nxt){
			v = edge[i].v; w = dis[u]+1;
			if(dis[v]>w){
				dis[v] = w;
				if(!vis[v]) vis[v]=1,q.push(v);
			}
		}
		
	}
}

int main() {
    scanf("%d%d",&n,&d);
    while(getchar()!='\n');
    for(int i=1;i<=n;i++)  a[i]=getchar();
    for(int i=1;i<=n;i++)
        if(a[i]=='1')  for(int j=1;j<=d&&i+j<=n;j++)  add(i,i+j);
    spfa();
    if(dis[n]==INF)  puts("-1");
    else  printf("%d",dis[n]);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • 区间更新与点值

    用户2965768
  • Java实现图片的滤镜效果滤镜实现总结

    在移动端或者在web开发时处理图片都是一件麻烦的事儿。我调研过很多library,特别是在移动端处理图片时动不动都需要使用 C++ 或者 OpenCV。这对于 ...

    fengzhizi715
  • Java中实现找到两个数组交集的2种方法,开发实用

    1、用HashSet实现的解决方法 实例代码如下: public int[] intersection(int[] nums1, int[] nums2) { ...

    用户1289394
  • 1061 判断题 (15 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 05:Cave Cows 1 洞穴里的牛之一

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 很少人知道其实奶牛非常喜欢到洞穴里面去探险。     洞窟里有N...

    attack
  • 图像处理卷积算法实现

      今天心血来潮,想把传统的卷积算法实现一份不采用各种加速方式,仅优化算法逻辑的纯净版本。 写完发现性能还可以,特发出来分享之,若有博友在此基础上,进行了再次优...

    cpuimage
  • 5971 打击犯罪

    题目描述 Description 某个地区有n(n<=1000)个犯罪团伙,当地警方按照他们的危险程度由高到低给他们编号为1-n,他们有些团伙之间有直接联系,但...

    attack
  • 搜索专题

    POJ  Best Sequence http://poj.org/problem?id=1699 题意:给你n个字符窜,求其所能拼接的最短长度。 分析:预处理...

    用户1624346

扫码关注云+社区

领取腾讯云代金券