地址：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 10010 int 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; }