spfa+剪枝 或者 dij+手写堆+剪枝 UOJ 111

http://uoj.ac/problem/111

好像NOIP里面的题目...有好多都是...能通过xjbg剪枝来...AC题目的？

得好好学一下这些剪枝黑科技了...

思路：我觉得这位大佬说的很完善了：http://blog.csdn.net/herano/article/details/58639052

竟然能卡分块暴力...hack数据不良心...不过好像最坏情况的边实在是太多了，没办法改变MLE的结局...？（其实3000000还好吧？）

然后就是xjbg优化了，对每一个块删除重复跑的。对于step<=sqrt(n)的，我们如果找到了下一个块中存在step相同的，我们就不用再找了，好像就是这样= =。

然后spfa跑一波即可（竟然卡了dijstra，难道要手写堆吗？）

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker,"/STACK:102400000,102400000")

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn =  + ;

int n, m;

int d[maxn];

vector<int> G[maxn];

bool have[maxn][ + ];

int s, t;

bool vis[maxn];

int solve(){

    queue<int> que;

    memset(d, 0x7f, sizeof(d));

    d[s] = ;

    que.push(s);

    while (!que.empty()){

        int u = que.front();

        que.pop();

        vis[u] = false;

        for (int i = ; i < G[u].size(); i++){

            int step = G[u][i];

            for (int j = ; u + step * j < n; j++){

                int v = u + step * j;

                if (d[v] > d[u] + j){

                    d[v] = d[u] + j;

                    if (!vis[v]){

                        que.push(v);

                        vis[v] = true;

                    }

                }

                if (step <=  && have[v][step]) break;

            }

            for (int j = ; u - step * j >= ; j++){

                int v = u - step * j;

                if (d[v] > d[u] + j){

                    d[v] = d[u] + j;

                    if (!vis[v]){

                        que.push(v);

                        vis[v] = true;

                    }

                }

                if (step <=  && have[v][step]) break;

            }

        }

    }

    return d[t] == 0x7f7f7f7f ? - : d[t];

}

int main(){

    cin >> n >> m;

    for (int i = ; i < m; i++){

        int a, b; scanf("%d%d", &a, &b);

        if (i == ) s = a;

        if (i == ) t = a;

        G[a].pb(b);

        if (b <= ) have[a][b] = ;

    }

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

        sort(ALL(G[i]));

        G[i].erase(unique(ALL(G[i])), G[i].end());

    }

    printf("%d\n", solve());

    return ;

}