hdu 3191+hdu 1688(最短路+次短路）-白红宇

hdu 3191+hdu 1688(最短路+次短路）

阅读量：4972 次

发布时间：2019-06-12

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

题目链接：

题意：求出次短路的长度和条数

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 const int MAXN=55;  8 const int inf=1<<30;  9 struct Edge{ 10     int v,w; 11 }; 12 vector
           
            vet[MAXN]; 13 struct Node{ 14 int v,dist; 15 int mark;//标记，1为最短路，2为次短路； 16 bool operator < (const Node &p) const { 17 if(p.dist!=dist) 18 return p.dist
            
             Q; 54 Node p,q; 55 dist[start][1]=0; 56 dp[start][1]=1; 57 p.dist=0,p.mark=1,p.v=start; 58 Q.push(p); 59 while(!Q.empty()){ 60 p=Q.top(); 61 Q.pop(); 62 if(visited[p.v][p.mark])continue; 63 //if(dist[p.v][p.mark]!=p.dist)continue; 64 visited[p.v][p.mark]=true; 65 for(int i=0;i

题目链接：

题意：求出最短路的条数比最短路大1的次短路的条数和，基本和上题一样，只是最后多了一个判断是否dist[e][1]+1==dist[e][2];

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int MAXN=1000+10; 7 const int inf=1<<30; 8 struct Edge{ 9     int v,w;10 };11 vector
          
           vet[MAXN];12 struct Node{13     int v,dist;14     int mark;15     bool operator < (const Node &p)const {16         return p.dist
           
            Q;34 Node p,q;35 p.dist=0,p.mark=1,p.v=start;36 Q.push(p);37 while(!Q.empty()){38 p=Q.top();39 Q.pop();40 if(visited[p.v][p.mark])continue;41 visited[p.v][p.mark]=true;42 for(int i=0;i