BZOJ2259 [Oibh]新型计算机

话说hzwer你在坑爹？、、、

我按照你的建图交了上去，发现WA。

开始检查= =。。。过了好久，突然觉得画风不对。。。hzwer您建图错了啊！！！

后来看了看zky的终于知道了怎么回事>_<

 /**************************************************************

     Problem: 2259

     User: rausen

     Language: C++

     Result: Accepted

     Time:3220 ms

     Memory:52884 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <queue>

 using namespace std;

 typedef long long ll;

 const int N = ;

 const int M = ;

 int n, tot;

 int dis[N], first[N];

 bool vis[N], pre[N], nxt[N];

 struct edges {

     int next, to, v;

     edges() {}

     edges(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {}

 } e[M];

 struct heap_node {

     int v, to;

     heap_node() {}

     heap_node(int _v, int _to) : v(_v), to(_to) {}

     inline bool operator < (const heap_node &b) const {

         return v > b.v;

     }

 };

 priority_queue <heap_node> h;

 inline int read() {

     int x = ;

     char ch = getchar();

     while (ch < '' || '' < ch)

         ch = getchar();

     while ('' <= ch && ch <= '') {

         x = x *  + ch - '';

         ch = getchar();

     }

     return x;

 }

 void add_edge(int x, int y, int z) {

     e[++tot] = edges(first[x], y, z);

     first[x] = tot;

 }

 inline void add_to_heap(const int p) {

     for (int x = first[p]; x; x = e[x].next)

         if (dis[e[x].to] == -)

             h.push(heap_node(e[x].v + dis[p], e[x].to));

 }

 void Dijkstra(int S) {

     memset(dis, -, sizeof(dis));

     while (!h.empty()) h.pop();

     dis[S] = , add_to_heap(S);

     int p;

     while (!h.empty()) {

         if (dis[h.top().to] != -) {

             h.pop();

             continue;

         }

         p = h.top().to;

         dis[p] = h.top().v;

         h.pop();

         add_to_heap(p);

     }

 }

 int main() {

     int i, j, x;

     n = read();

     for (i = ; i <= n; ++i) {

         x = read();

         for (j = i + ; j <= min(i + x + , n) && !pre[j]; ++j)

             pre[j] = , add_edge(j, j - , );

         for (j = i + x + ; j <= n && !nxt[j]; ++j)

             nxt[j] = , add_edge(j, j + , );

         if (i + x <= n) add_edge(i, i + x + , );

         else add_edge(i, n + , i + x - n);

     }

     Dijkstra();

     printf("%d\n", dis[n + ]);

     return ;

 }