POJ--3268--Silver Cow Party【SPFA+邻接表】-白红宇

POJ--3268--Silver Cow Party【SPFA+邻接表】

阅读量：4974 次

发布时间：2019-06-12

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

题意：一些牛要去某一点參加聚会，然后再回到自己家，路是单向的，问花费时间最多的那头牛最少须要花费多长时间。

思路：从聚会地点返回，相当于是从某一点到其它各个点的最短路径。从牛的家中走到聚会地点，能够把路径反过来变成从聚会地点到各个点的最短路径，两个最短路径值加起来就是每头牛所花费的最小时间，找出最大的就可以。

我用了两个邻接表存路径，事实上这道题用邻接矩阵存更好做，矩阵横纵坐标翻转就把路径反转了，我用SPFA写想练练手，一直都不会手写SPFA，做几道题找找感觉。

AC竟然用时0MS。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      using namespace std;#define PI acos(-1.0)#define MAXN 100100#define eps 1e-7#define INF 0x7FFFFFFF#define seed 131#define ll long long#define ull unsigned ll#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1struct node{ int u,v,next;}edge[MAXN],redge[MAXN];int head[MAXN],rhead[MAXN],dist[MAXN],vis[MAXN],ans[MAXN];int cnt,rcnt,n,m,x;void add_edge(int a,int b,int c){ edge[cnt].u = b; edge[cnt].v = c; edge[cnt].next = head[a]; head[a] = cnt++; redge[rcnt].u = a; redge[rcnt].v = c; redge[rcnt].next = rhead[b]; rhead[b] = rcnt++;}void spfa(int type){ int i,j; for(i=1;i<=n;i++){ dist[i] = INF; } dist[x] = 0; memset(vis,0,sizeof(vis)); vis[x] = 1; queue
                      
                       q; q.push(x); while(!q.empty()){ int temp = q.front(); q.pop(); vis[temp] = 0; for(i=type?rhead[temp]:head[temp];i!=-1;i=type?redge[i].next:edge[i].next){ int lu = type?redge[i].v:edge[i].v; if(lu+dist[temp]
                       
                        maxm) maxm = ans[i]; } printf("%d\n",maxm); return 0;}

转载于:https://www.cnblogs.com/hrhguanli/p/3964836.html

你可能感兴趣的文章