[bzoj3482][COCI2013]hiperprostor

首先可以想到如果对于所有的i可以求出起点到终点经过的所有路径中经过i个x边的最短路径，就可以使用凸包维护出答案。对于求解所有路径中经过i个x边的路径，由于i超过n之后没有意义，所以我们可以裂点之后跑dijsktra。

但是这个算一下会发现有点卡，如果使用一般的二叉堆来优化dijsktra，时间复杂度为$O(qnm\lg n)$的（据说也能过），其实我们可以使用基数堆来优化dijsktra把时间复杂度变为$O(qn^2\lg C+qnm)$。

\#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
struct RadixHeap{
    int top;
    struct Key{int key,pre,nxt,pos; }list[600005];
    struct Node{int l,r,head; }heap[35];
    inline void clear(){ heap[top=1]=(Node){0,(int)1e9,0}; }
    inline void insert(int pos,int x,int key){
        list[heap[pos].head].pre=x;
        list[x]=(Key){key,0,heap[pos].head,pos};
        heap[pos].head=x;
    }
    inline void erase(int x){
        heap[list[x].pos].head==x?heap[list[x].pos].head=list[x].nxt
            :list[list[x].pre].nxt=list[x].nxt;
        list[list[x].nxt].pre=list[x].pre;
    }
    inline void decrease(int x,int key){
        erase(x);
        int pos=list[x].pos;
        while(heap[pos].l>key) ++pos;
        insert(pos,x,key);
    }
    inline int query(){
        while(heap[top].head==0) --top;
        while(heap[top].l!=heap[top].r){
            int l=heap[top].l,r=heap[top].r,mid=l+r>>1;
            heap[top].l=mid+1;
            heap[++top]=(Node){l,mid,0};
            for(int j=heap[top-1].head;j!=0;){
                int k=list[j].nxt;
                if(heap[top-1].l>list[j].key)
                    erase(j),insert(top,j,list[j].key);
                j=k;
            }
            if(heap[top].head==0) --top;
        }
        int ret=heap[top].head;
        erase(ret);
        return ret;
    }
}rheap;
struct ConvexHull{
    struct Key{ ll k,b,pos; }stk[505];
    int top;
    void clear(){ top=0;} 
    ll opera(ll pos,Key x){ return x.k*pos+x.b; }
    void insert(Key x){
        if(top==0||opera(stk[1].pos,x)<opera(stk[1].pos,stk[1]))
            stk[top=1]=(Key){x.k,x.b,1};
        else{
            while(opera(stk[top].pos,x)<opera(stk[top].pos,stk[top]))
                --top;
            ll left=stk[top].pos,right=5e8;
            while(left<right){
                ll mid=left+right>>1;
                if(opera(mid,x)<opera(mid,stk[top])) right=mid;
                else left=mid+1;
            }
            stk[++top]=(Key){x.k,x.b,right};
        }
    }
    void query(ll dtop){
        ll ret1=0,ret2=0,i;
        for(i=1;i<top&&opera(stk[i+1].pos-1,stk[i])<dtop;++i){
            ll cnt=stk[i+1].pos-1;
            ret2+=cnt-stk[i].pos+1;
            ret1+=stk[i].k*(cnt*(cnt+1)/2-(stk[i].pos-1)*stk[i].pos/2)
                +stk[i].b*(cnt-stk[i].pos+1);
        }
        ll cnt=(dtop-stk[i].b)/stk[i].k;
        if(opera(cnt,stk[i])==dtop) --cnt;
        if(cnt>=stk[i].pos){
            ret2+=cnt-stk[i].pos+1;
            ret1+=stk[i].k*(cnt*(cnt+1)/2-(stk[i].pos-1)*stk[i].pos/2)
                +stk[i].b*(cnt-stk[i].pos+1);
        }
        ret2+=1,ret1+=dtop;
        printf("%lld %lld\n",ret2,ret1);
    }
}ch;
struct Edge{
    int to,nxt,key;
}edge[10005];
int head[505],dis[600005],top_edge=-1,n,m;
inline void add_edge(int x,int y,int key){
    edge[++top_edge]=(Edge){y,head[x],key};
    head[x]=top_edge;
}
inline int id(int x,int y){ return (x-1)*(n+1)+y+1; }
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y,key=0; scanf("%d%d",&x,&y);
        char s[100]; scanf("%s",s+1);
        if(s[1]=='x') key=-1;
        else{ 
            int len=strlen(s+1);
            for(int i=1;i<=len;++i)
                key=(key<<3)+(key<<1)+s[i]-'0';
        }
        add_edge(x,y,key);
    }
    int q; scanf("%d",&q);
    while(q--){
        int x,y; scanf("%d%d",&x,&y);
        for(int i=1;i<=n*(n+1);++i)
            dis[i]=i==id(x,0)?0:1e9;
        rheap.clear();
        for(int i=1;i<=n*(n+1);++i)
            rheap.insert(1,i,dis[i]);
        for(int i=1;i<=n*(n+1);++i){
            int x=rheap.query();
            int t=(x-1)/(n+1)+1,d=(x-1)%(n+1);
            for(int j=head[t];j!=-1;j=edge[j].nxt){
                int y=edge[j].to;
                if(edge[j].key==-1){
                    if(d==n) break;
                    int y1=id(y,d+1);
                    if(dis[x]<dis[y1]){
                        dis[y1]=dis[x];
                        rheap.decrease(y1,dis[y1]);
                    }
                }else{
                    int y1=id(y,d);
                    if(dis[x]+edge[j].key<dis[y1]){
                        dis[y1]=dis[x]+edge[j].key;
                        rheap.decrease(y1,dis[y1]);
                    }
                }
            }
        }
        int dtop=dis[id(y,0)];
        ch.clear();
        for(int i=n;i>=1;--i)
            if(dis[id(y,i)]<(int)1e9) 
                ch.insert((ConvexHull::Key){i,dis[id(y,i)],0});
        if(ch.top==0&&dtop==(int)1e9) puts("0 0");
        else if(dtop==(int)1e9) puts("inf");
        else ch.query(dtop);
    }
    return 0;
}