UVA 11374 Airport Express 最短路-白红宇

UVA 11374 Airport Express 最短路

阅读量：7188 次

发布时间：2019-06-29

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

分别求出以S和E为起点的最短路，然后枚举每一张商务票 (u,v) 求 A(u) + w(u,v) + B(v)

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
                    
                      pii;#define pb(a) push(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template
                     
                       T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c));}template
                      
                        T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c));}void debug() {#ifdef ONLINE_JUDGE#else freopen("d:\\in1.txt","r",stdin); freopen("d:\\out1.txt","w",stdout);#endif}int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}const int maxn=505;struct Edge{ int u,v,dist;};struct HeapNode{ int d,u; bool operator < (const HeapNode &ant) const { if(d!=ant.d)return d>ant.d; else return u>ant.u; }};struct dijksta{ int n; vector
                       
                         g[maxn]; vector
                        
                          edge; int done[maxn]; void init(int n) { this->n=n; for(int i=1;i<=n;i++) g[i].clear(); edge.clear(); } void add(int u,int v,int dist) { Edge e=(Edge){u,v,dist}; edge.push_back(e); g[u].push_back(edge.size()-1); } void solve(int *d,int *p,int s) { priority_queue
                         
                           q; memset(done,0,sizeof(done)); for(int i=1;i<=n;i++) d[i]=INF; d[s]=0; p[s]=-1; q.push((HeapNode){ 0,s}); while(!q.empty()) { HeapNode x=q.top();q.pop(); int u=x.u; if(done[u])continue; done[u]=1; for(int i=0;i

s; Edge &e=Ticket[minid]; for(int u=e.u;u!=-1;u=pf[u]) s.push(u); while(!s.empty()) { int u=s.top();s.pop(); printf("%d",u); if(u!=e.u)printf(" "); } for(int u=e.v;u!=-1;u=pg[u]) printf(" %d",u); printf("\n"); printf("%d\n%d\n",e.u,mint); } } return 0;}

View Code

转载于:https://www.cnblogs.com/BMan/p/3632895.html

你可能感兴趣的文章