POJ3255次短路-白红宇

POJ3255次短路

阅读量：4619 次

发布时间：2019-06-09

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

POJ3255

题意：给定一个图，求从1到n的次短路

分析：我们需要在dijkstra上作出一些修改，首先，到某个顶点v的次短路要么是到其他某个顶点u的最短路在加上u到v的边，要么是到v的次短路再加上u到v的边，因此我们需要记录的是最短和次短路。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 const int maxn=5050;15 const int INF=1<<30;16 struct edge17 {18 int to,cost; //顶点号和距离19 };20 typedef pair
                  
                    P; //first是最短距离，second是顶点编号21 vector
                   
                     g[maxn];22 int n,r; //顶点数，边数23 int d[maxn]; //最短距离24 int d2[maxn]; //次短距离25 void dijkstra(int s)26 {27 priority_queue
                    
                     , greater
                      > que;28 fill(d,d+1+n,INF);29 fill(d2,d2+1+n,INF);30 d[s]=0;31 que.push(P(0,s));32 33 while(!que.empty()){34 P p=que.top(); que.pop();35 int v=p.second,t=p.first;36 if(d2[v]
                      
                       dist){41 swap(d[e.to],dist);42 que.push(P(d[e.to],e.to));43 }44 if(d2[e.to]>dist&&d[e.to]
                       
                        >n>>r)54 {55 for(int i=0;i

View Code

转载于:https://www.cnblogs.com/wolf940509/p/5589325.html

你可能感兴趣的文章