BZOJ4070: [Apio2015]雅加達的摩天樓

暴力建圖大概誰都會吧（雖然我一開始建錯了[捂臉熊]），所以還是說一下。
從每個起點枚舉走的步數，連對應長度的邊，跑dij即可（為什麼那麼多人自信spfa？）
這樣最差情況下是n^2條邊的…肯定跑不過所有的數據。
注意到當步長>sqrt(n)的時候，建出的邊只有sqrt(n)條，所以步長>sqrt(n)的時候解決了，那麼步長 < sqrt(n)呢？
也就是說每個點向外的步長 < sqrt(n)的邊數不會超過sqrt(n)條，很多邊都是重合的，只需要將它們合並即可。
總復雜度(n* sqrt(n) *logn)
對了，0x3f3f3f3f少打一個f可是會身敗名裂的…

#include
#include
#include
#include
#include
#include
//by:MirrorGray
using namespace std;
const int N=31111,M=12111111,inf=0x3f3f3f3f;
int dis[N],fz[N];
int tot=-1,head[N],ver[M],nxt[M],len[M];
struct doge{
    int b,p,po;
    bool operator <(const doge&c)const{
        if(p!=c.p)return pb.dis;
    }
};
priority_queue  q;

void add(int x,int y,int z){
    nxt[++tot]=head[x];head[x]=tot;ver[tot]=y;len[tot]=z;
}

int dij(int x,int y){
    static bool vis[N];
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    q.push(node(x,0));dis[x]=0;
    while(!q.empty()){
        int x=q.top().x;q.pop();
        if(vis[x])continue;
        vis[x]=true;
        for(int i=head[x];~i;i=nxt[i])
        if(dis[ver[i]]>dis[x]+len[i]){
            dis[ver[i]]=dis[x]+len[i];
            q.push(node(ver[i],dis[ver[i]]));
        }
    }
    return dis[y]==inf?-1:dis[y];//身敗名裂… 
}

int main(){
    memset(head,-1,sizeof(head));
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&p[i].b,&p[i].p);
        p[i].po=p[i].b%p[i].p;
    }
    int bi=p[1].b,en=p[2].b;
    sort(p+1,p+1+m);
    for(int i=1,j=1;i<=m;){
        while(j<=m && p[i].po==p[j].po && p[i].p==p[j].p)j++;
        int tmp=p[i].p,top=0;
        while(i=0 && k>=fz[sh-1];k-=tmp)add(fz[sh],k,(fz[sh]-k)/tmp);
        for(int sh=top;sh;sh--)
        for(int k=fz[sh]+tmp;k