1 /************************************************************** 2     Problem: 2259 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:3220 ms 7     Memory:52884 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12 #include <cstring>13 #include <queue>14  15 using namespace std;16 typedef long long ll;17 const int N = 1000005;18 const int M = 3000005;19  20 int n, tot;21 int dis[N], first[N];22 bool vis[N], pre[N], nxt[N];23  24 struct edges {25     int next, to, v;26     edges() {}27     edges(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {}28 } e[M];29  30 struct heap_node {31     int v, to;32     heap_node() {}33     heap_node(int _v, int _to) : v(_v), to(_to) {}34  35     inline bool operator < (const heap_node &b) const {36         return v > b.v;37     }38 };39  40 priority_queue <heap_node> h;41  42 inline int read() {43     int x = 0;44     char ch = getchar();45     while (ch < ‘0‘ || ‘9‘ < ch)46         ch = getchar();47     while (‘0‘ <= ch && ch <= ‘9‘) {48         x = x * 10 + ch - ‘0‘;49         ch = getchar();50     }51     return x;52 }53  54 void add_edge(int x, int y, int z) {55     e[++tot] = edges(first[x], y, z);56     first[x] = tot;57 }58  59 inline void add_to_heap(const int p) {60     for (int x = first[p]; x; x = e[x].next)61         if (dis[e[x].to] == -1)62             h.push(heap_node(e[x].v + dis[p], e[x].to));63 }64  65 void Dijkstra(int S) {66     memset(dis, -1, sizeof(dis));67     while (!h.empty()) h.pop();68     dis[S] = 0, add_to_heap(S);69     int p;70     while (!h.empty()) {71         if (dis[h.top().to] != -1) {72             h.pop();73             continue;74         }75         p = h.top().to;76         dis[p] = h.top().v;77         h.pop();78         add_to_heap(p);79     }80 }81  82 int main() {83     int i, j, x;84     n = read();85     for (i = 1; i <= n; ++i) {86         x = read();87         for (j = i + 1; j <= min(i + x + 1, n) && !pre[j]; ++j)88             pre[j] = 1, add_edge(j, j - 1, 1);89         for (j = i + x + 1; j <= n && !nxt[j]; ++j)90             nxt[j] = 1, add_edge(j, j + 1, 1);91         if (i + x <= n) add_edge(i, i + x + 1, 0);92         else add_edge(i, n + 1, i + x - n);93     }94     Dijkstra(1);95     printf("%d\n", dis[n + 1]);96     return 0;97 }