HDU - 1688 Sightseeing 最短路和次短路计数-白红宇的个人博客

HDU - 1688 Sightseeing 最短路和次短路计数

发布日期：2021-09-25 23:57:58 浏览次数：10 分类：技术文章

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

不是很难的一个题，因为只是求次短路，用k短路求就有点大材小用了，所以可以用dijkstra求次短路。

只需要在原来松弛的时候进行改动：

(1) 当前权值比最短路小，那么把当前最短路的数据复制到次短路，让后更新最短路

(2) 当前权值等于最短路，那么直接将次数加起来

(3) 当前权值比次短路小，那么直接更新次短路

(4) 当前权值等于次短路，那么直接将次数加起来

wa了20多发，照网上代码改了好几个，一模一样都能wa掉，结果发现是我自己写的变量有歧义了。。测试数据用的t，终点也用的t，直接当场去世。以后还是用 _ 这样的当变量吧~~~

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1010,M=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m,s,t;int e[M],ne[M],w[M],h[N*2],idx;int dis[2][N],cnt[2][N];bool st[2][N];struct Node{ int u,w,f; friend bool operator < (Node a , Node b) { return a.w>b.w; }};void add(int a,int b,int c){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}void init(){ idx=0; memset(cnt,0,sizeof (cnt)); memset(st,false,sizeof (st)); memset(h,-1,sizeof (h)); for(int i=1;i<=n;i++) dis[1][i]=dis[0][i]=2e9+7;}void dijkstra(){ priority_queue
                
                 q; q.push({ s,0,0}); dis[0][s]=0; cnt[0][s]=1; while(q.size()) { Node t=q.top(); q.pop(); int u=t.u,dd=t.w,p=t.f; if(st[p][u]) continue; st[p][u]=true; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; int d=dis[p][u]+w[i]; if(dis[0][j]>dis[p][u]+w[i]) { dis[1][j]=dis[0][j]; cnt[1][j]=cnt[0][j]; dis[0][j]=dis[p][u]+w[i]; cnt[0][j]=cnt[p][u]; q.push({ j,dis[0][j],0}); q.push({ j,dis[1][j],1}); } else if(dis[0][j]==dis[p][u]+w[i]) cnt[0][j]+=cnt[p][u]; else if(dis[1][j]>dis[p][u]+w[i]) { dis[1][j]=dis[p][u]+w[i]; cnt[1][j]=cnt[p][u]; q.push({ j,dis[1][j],1}); } else if(dis[1][j]==dis[p][u]+w[i]) cnt[1][j]+=cnt[p][u]; } }}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); int _; scanf("%d",&_); while(_--) { scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } scanf("%d%d",&s,&t); dijkstra(); if(dis[1][t]==dis[0][t]+1) printf("%d\n",cnt[1][t]+cnt[0][t]); else printf("%d\n",cnt[0][t]); } return 0;}/*4 41 2 11 3 22 4 13 4 21 4*/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/107741620 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Reverse and Swap CodeForces - 1401 F 线段树 + 思维

下一篇：POJ - 3723 Conscription 最小生成树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章