Gym

题目链接：http://codeforces.com/gym/101147/problem/E

题意：当人在第i个商店时，他可以向左或向右跳di段距离到达另一个商店（在范围之内），一个商店为一段距离。问：对于每一个商店，跳到最后一个商店最少需要跳几次？

题解：题目实际上是求最短距离，而且边权为1，所以可以直接用bfs。由于是求每个点到最后一个点的最短距离，那么可以反向建图，将最后一个点设为起始点，然后向前跑。对于跑不到的点，回到题目上说，实际就是这个商店不能到达最后一个商店。

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <string>
  6 #include <vector>
  7 #include <map>
  8 #include <set>
  9 #include <queue>
 10 #include <sstream>
 11 #include <algorithm>
 12 using namespace std;
 13 #define pb push_back
 14 #define mp make_pair
 15 #define ms(a, b)  memset((a), (b), sizeof(a))
 16 //#define LOCAL
 17 #define eps 0.0000001
 18 typedef long long LL;
 19 const int inf = 0x3f3f3f3f;
 20 const int maxn = 100000+10;
 21 const int mod = 1000000007;
 22 
 23 vector <int > v[maxn];
 24 LL len[maxn];
 25 
 26 struct node
 27 {
 28     int  sta;
 29     LL  k;
 30 };
 31 queue<node>q;
 32 node now, e;
 33 
 34 int vis[maxn];
 35 int bfs(int be)
 36 {
 37     ms(vis,0);
 38     while(!q.empty())
 39         q.pop();
 40 
 41     now.sta = be;
 42     now.k = 0;
 43     vis[be] = 1;
 44     q.push(now);
 45     len[be] = 0;
 46     while(!q.empty())
 47     {
 48         now = q.front();
 49         q.pop();
 50 
 51         int big = v[now.sta].size();
 52         for(int i = 0; i<big; i++)
 53         {
 54             if(!vis[ v[now.sta][i] ])
 55             {
 56                 e.sta = v[now.sta][i] ;
 57                 e.k = now.k+1;
 58                 len[e.sta] = e.k;
 59                 
 60                 vis[e.sta ] = 1;
 61                 q.push(e);
 62             }
 63         }
 64     }
 65     return 0;
 66 }
 67 
 68 void solve()
 69 {
 70     int n;
 71     scanf("%d", &n);
 72     for(int i = 1; i<=n; i++)
 73         v[i].clear();
 74     for(int i=1;i<=n;i++)
 75     {
 76         int d;
 77         scanf("%d", &d);
 78         if(i-d>=1)  v[i-d].pb(i);//反向建图
 79         if(i+d<=n)  v[i+d].pb(i);
 80     }
 81 
 82     ms(len,-1);
 83     bfs(n);
 84     for(int i = 1; i<=n; i++)
 85         printf("%lld
",len[i]);
 86 }
 87 
 88 int main()
 89 {
 90     #ifdef LOCAL
 91          freopen("jumping.in", "r", stdin);
 92 //      freopen("output.txt", "w", stdout);
 93     #endif // LOCAL
 94 
 95     int T;
 96     scanf("%d", &T);
 97     while(T--){
 98         solve();
 99     }
100 
101     return 0;
102 }

View Code