CF910A The Way to Home SPFA(队列优化)
CF910A The Way to Home SPFA(队列优化)
用户2965768
发布于 2019-04-09 16:26:30
发布于 2019-04-09 16:26:30
题意翻译
题目描述
一只青蛙现在在一个数轴上，它现在要从点 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 的无空格字符串，由0和1组成，表示哪些点上有百合花（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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年03月31日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录