SGU 314 Shortest Paths-白红宇

SGU 314 Shortest Paths

阅读量：6544 次

发布时间：2019-06-24

本文共 4859 字，大约阅读时间需要 16 分钟。

题目链接：

题意：给出n个点m条边的有向图。输出从s到t的前K短路。

思路：首先，从t开始遍历一次得到每个点到t的最短路dis[i]，且得到一棵最短路树，即边<u,v,d>满足dis[u]=dis[v]+d。那么，从任意一个节点到t的最短路都对应最短路树上的一条路径。对于不在最短路树上的边e<u,v,d>，如果我们走了这条边，则长度要增加det(e)=d+dis[v]-dis[u]。那么，我们可以计算出所有不在最短路树上的边的det值。那么除最短路外的每一条路径都是走了若干条不在最短路树上的边，也就是dis[s]加了几个det。那么问题转化成每次选出一些det值，使得这些值的和依次递增。当然这些选出的det不能乱选，他们要在一条路径上。接下来，为每个点u建立一个小根堆H1(u)，H1(u)堆中的每个点是从u出发的非树边的det值。接着，对于树边<u,v>，我们要将H1(v)接在H1(u)下面得到H2(u)，且H2(u)还是一个小根堆。设H2(u)的根节点为head[u]，最后从head[s]开始得到前K个解。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define MP(x,y) make_pair(x,y)#define FOR0(i,x) for(i=0;i
                
                 =0;i--)#define DOW1(i,x) for(i=x;i>=1;i--)#define DOW(i,a,b) for(i=a;i>=b;i--)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%I64d",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%d\n",x);}void PR(i64 x) {printf("%I64d\n",x);}void PR(u32 x) {printf("%u\n",x);}void PR(double x) {printf("%.6lf\n",x);}void PR(char x) {printf("%c\n",x);}void PR(char *x) {printf("%s\n",x);}void PR(string x) {cout<
                 
                  <
                  
                    g[N],g1[N];Heap* nullNode;Heap* head[N];void Add(int u,int v,int dis){ node* E=new node; E->u=u; E->v=v; E->dis=dis; g[u].pb(E); g1[v].pb(E);}void input(){ RD(n,m,K); RD(s,t); int u,v,dis; while(m--) { RD(u,v,dis); Add(u,v,dis); }}queue
                   
                     dfsQ;struct NODE{ int v; i64 dis; Heap* H; node* E; NODE(){} NODE(i64 _dis,int _v,node* _E) { v=_v; dis=_dis; E=_E; } NODE(Heap* _H,i64 _dis) { H=_H; dis=_dis; } friend bool operator<(NODE a,NODE b) { return a.dis>b.dis; }};void dijkstra(){ clr(dis,-1); priority_queue
                    
                      Q; Q.push(NODE(0,t,(node*)NULL)); NODE p; vector
                     
                      ::iterator it; while (!Q.empty()) { p=Q.top(); Q.pop(); if(dis[p.v]!=-1) continue; dis[p.v]=p.dis; Next[p.v]=p.E; dfsQ.push(p.v); for(it=g1[p.v].begin();it!=g1[p.v].end();it++) { Q.push(NODE(p.dis+(*it)->dis,(*it)->u,*it)); } }}int cmp(Heap* a,Heap* b){ return a->edge->dis>b->edge->dis;}Heap* creat(Heap* curNode,Heap* newNode){ if(curNode==nullNode) return newNode; Heap* root=new Heap; memcpy(root,curNode,sizeof(Heap)); if(newNode->edge->dis
                      
                       edge->dis) { root->edge=newNode->edge; root->child[2]=newNode->child[2]; root->child[3]=newNode->child[3]; newNode->edge=curNode->edge; newNode->child[2]=curNode->child[2]; newNode->child[3]=curNode->child[3]; } if(root->child[0]->dep
                       
                        child[1]->dep) { root->child[0]=creat(root->child[0],newNode); } else { root->child[1]=creat(root->child[1],newNode); } root->dep=max(root->child[0]->dep,root->child[1]->dep)+1; return root;}void build(){ nullNode=new Heap; nullNode->dep=0; nullNode->edge=new node; nullNode->edge->dis=INF; fill(nullNode->child,nullNode->child+4,nullNode); vector
                        
                          V; Heap* p; vector
                         
                          ::iterator it; int u,v,i; while(!dfsQ.empty()) { u=dfsQ.front(); dfsQ.pop(); if(Next[u]==NULL) head[u]=nullNode; else head[u]=head[Next[u]->v]; V.clear(); for(it=g[u].begin();it!=g[u].end();it++) { v=(*it)->v; if(dis[v]==-1) continue; (*it)->dis+=dis[v]-dis[u]; if(Next[u]!=*it) { p=new Heap; fill(p->child,p->child+4,nullNode); p->dep=1; p->edge=*it; V.pb(p); } } if(SZ(V)==0) continue; make_heap(V.begin(),V.end(),cmp); FOR0(i,SZ(V)) { if(2*i+1
                          
                           child[2]=V[2*i+1]; else V[i]->child[2]=nullNode; if(2*i+2
                           
                            child[3]=V[2*i+2]; else V[i]->child[3]=nullNode; } head[u]=creat(head[u],V.front()); }}void print(){ priority_queue
                            
                              Q; if(dis[s]==-1) puts("NO"); else { PR(dis[s]); if(head[s]!=nullNode) Q.push(NODE(head[s],dis[s]+head[s]->edge->dis)); } K--; NODE p,q; int i; while(K--) { if(Q.empty()) { puts("NO"); continue; } p=Q.top(); Q.pop(); PR(p.dis); if(head[p.H->edge->v]!=nullNode) { q.H=head[p.H->edge->v]; q.dis=p.dis+q.H->edge->dis; Q.push(q); } FOR0(i,4) if(p.H->child[i]!=nullNode) { q.H=p.H->child[i]; q.dis=p.dis-p.H->edge->dis+p.H->child[i]->edge->dis; Q.push(q); } }}int main(){ input(); dijkstra(); build(); print(); return 0;}

转载地址：http://oeodo.baihongyu.com/

你可能感兴趣的文章