nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

uoj111

优化建图即可，对图分块，但是这样还是过不了，因为常数过大，不建图跑dij还是会tle，要用spfa才能过

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
typedef pair<int,int> pii;

int main(){
    int n,m; scanf("%d%d",&n,&m);
    int sqr=200;
    vector<vector<int> >dog(n),havedog(n,vector<int>(sqr,0));
    int src=0,dst=1;
    for(int i=0;i<m;i++) {
        int x,y; scanf("%d%d",&x,&y);
        if(i==0) src=x;
        if(i==1) dst=x;
        dog[x].push_back(y);// a dog at x can jump y step
        if(y<sqr)havedog[x][y]=1;
    }
    for(int i=0;i<n;i++) {
        sort(dog[i].begin(),dog[i].end());
        dog[i].erase(unique(dog[i].begin(),dog[i].end()),dog[i].end());
    }
    // dij
    vector<int>dist(n,2e9);
    __gnu_pbds::priority_queue<pii,greater<pii>,__gnu_pbds::thin_heap_tag> q;
    dist[src]=0;
    q.push(pii(dist[src],src));
    while(!q.empty()){
        int u=q.top().second,dis=q.top().first;
        q.pop();
        if(dist[u]!=dis)continue;
        for(int jump:dog[u]){
            for(int d=1;u+d*jump<n;d++){
                if(dist[u+d*jump]>dist[u]+d){
                    dist[u+d*jump]=dist[u]+d;
                    q.push(pii(dist[u+d*jump],u+d*jump));
                }
                if(jump<sqr&&havedog[u+d*jump][jump]) break;
            }
            for(int d=1;u-d*jump>=0;d++){
                if(dist[u-d*jump]>dist[u]+d){
                    dist[u-d*jump]=dist[u]+d;
                    q.push(pii(dist[u-d*jump],u-d*jump));
                }
                if(jump<sqr&&havedog[u-d*jump][jump]) break;
            }
        }
    }
    if(dist[dst]==2e9) cout<<-1<<endl;
    else cout<<dist[dst]<<endl;
}