K短路新姿势

地址：http://blog.csdn.net/wyfcyx_forever/article/details/45875055

#include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>#include<queue>using namespace std;#define mp make_pair#define pb push_back#define inf 0x3f3f3f3f#define N 10010int n,m,K;typedef long long ll;typedef pair<int,int> pii;struct SegmentTree{    pii s[32768];    int M;    inline void init(int _siz)    {        for(M=1; M<(_siz+2); M<<=1);        for(int i=0; i<(M<<1); ++i)            s[i]=mp(inf,0);    }    inline void modify(int x,int y)    {        for(s[x+M]=mp(y,x),(x+=M)>>=1; x; x>>=1)            s[x]=min(s[x<<1],s[x<<1^1]);    }    inline int getid()    {        return s[1].second;    }} Seg;struct Graph{    static const int V=N;    static const int E=100010;    int head[V],next[E],end[E],len[E],ind;    inline void reset()    {        ind=0;        memset(head,0,sizeof head);    }    inline void addedge(int a,int b,int c)    {        int q=++ind;        end[q]=b,next[q]=head[a];        head[a]=q,len[q++]=c;    }} g,_g,tree;int d[N];inline void dijkstra(int s,Graph&g){    memset(d,0x3f,sizeof d);    Seg.init(n);    d[s]=0;    Seg.modify(s,0);    for(int i=1; i<=n; ++i)    {        int x=Seg.getid();        for(int j=g.head[x]; j; j=g.next[j])        {            if(d[g.end[j]]>d[x]+g.len[j])            {                d[g.end[j]]=d[x]+g.len[j];                Seg.modify(g.end[j],d[g.end[j]]);            }        }        Seg.modify(x,inf);    }}int pa[N];struct Node{    Node*l,*r;    int v,tail,dist;    Node():dist(0) {}} mempool[1000010],*P=mempool,Tnull,*null=&Tnull;inline Node*newnode(int _v,int _tail){    P->l=P->r=null;    P->v=_v;    P->tail=_tail;    P->dist=1;    return P++;}inline void copy(Node*&p,Node*q){    if(q==null) p=null;    else *p=*q;}inline Node*merge(Node*p,Node*q){    Node*s=P++;    if(p==null||q==null)    {        copy(s,p==null?q:p);        return s;    }    if(p->v>q->v) swap(p,q);    copy(s,p);    s->r=merge(p->r,q);    if(s->l->dist<s->r->dist)        swap(s->l,s->r);    s->dist=s->r->dist+1;    return s;}Node*root[N];struct State{    ll ldist;    Node*ledge;    State():ldist(0ll),ledge(null) {}    State(ll _ldist,Node* _ledge):ldist(_ldist),ledge(_ledge) {}    bool Operator<(const State&B)const    {        return ldist>B.ldist;    }};PRiority_queue<State> Q;bool treeedge[100010];int main(){    cin>>n>>m>>K;    int i,j,a,b,c;    g.reset();    _g.reset();    for(i=1; i<=m; ++i)    {        scanf("%d%d%d",&a,&b,&c);        g.addedge(a,b,c);        _g.addedge(b,a,c);    }    dijkstra(n,_g);    for(i=1; i<n; ++i)        for(j=g.head[i]; j; j=g.next[j])            if(d[i]==d[g.end[j]]+g.len[j])            {                pa[i]=g.end[j];                treeedge[j]=1;                break;            }    tree.reset();    for(i=1; i<n; ++i) tree.addedge(pa[i],i,0);    queue<int>q;    q.push(n);    Node*p;    root[0]=null;    while(!q.empty())    {        i=q.front();        q.pop();        root[i]=merge(null,root[pa[i]]);        for(j=g.head[i]; j; j=g.next[j])            if(!treeedge[j])            {                p=newnode(g.len[j]-(d[i]-d[g.end[j]]),g.end[j]);                root[i]=merge(root[i],p);            }        for(j=tree.head[i]; j; j=tree.next[j])            q.push(tree.end[j]);    }    if(K==1) cout<<d[1]<<endl;    else    {        --K;        Q.push(State(d[1]+root[1]->v,root[1]));        State tmp;        ll ldist;        Node*ledge;        for(int i=1; i<=K; ++i)        {            tmp=Q.top();            Q.pop();            ldist=tmp.ldist;            ledge=tmp.ledge;            if(i==K)            {                cout<<ldist<<endl;                break;            }            Q.push(State(ldist+root[ledge->tail]->v,root[ledge->tail]));            if(ledge->l!=null)                Q.push(State(ldist-ledge->v+ledge->l->v,ledge->l));            if(ledge->r!=null)                Q.push(State(ldist-ledge->v+ledge->r->v,ledge->r));        }    }    return 0;}