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

题意：

陪女票逛街，有n个商店，每个商店有个di，可以从第i个商店跳到i-di或者i+di个，但是不能超出商店的编号范围，1~n。

思路：

最短啊，做之前想想再写好么，dij是单源点最短路，这个单源点是从一个固定的点到达其他各个点的最短路。这个题固定的点是那个？他女票所在的商店N，推入边的时候也是要从i-di或者i+di到i，是反向建边的，因为你的目的是想到N点，但是寻找路是从N固定开始找1到N的最短路。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int Ni = 100010;const int INF = 0x3f3f3f3f;struct node{    int x,d;    node() {}    node(int a,int b)    {        x=a;        d=b;    }    bool operator < (const node & a) const    {        return d > a.d;    }};vector
         
           eg[Ni];int dis[Ni],n,T;void Dijkstra(int s){    int i;    for(i=0; i<=n; i++) dis[i]=INF;    dis[s]=0;    //用优先队列优化    priority_queue
          
            q; q.push(node(s,dis[s])); while(!q.empty()) { node x=q.top(); q.pop(); for(i=0; i
           
            x.d+y.d) { dis[y.x]=x.d+y.d; q.push(node(y.x,dis[y.x])); } } }}int main(){ freopen("jumping.in","r",stdin); scanf("%d",&T); while(T--) { while(~scanf("%d",&n)) { for(int i=0; i<=n; i++) eg[i].clear(); for(int i = 1; i <=n; i++) { int dd; scanf("%d",&dd); if(i-dd>0) eg[i-dd].push_back(node(i,1)); if(i+dd<=n) eg[i+dd].push_back(node(i,1)); } Dijkstra(n); for(int i = 1; i <= n; i++) if(dis[i]