T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks

网上看到的spfa的实现,很清晰。Orz~~

#include <cstdio>
#include 
<cstring>
const int maxn = 10000+1;
const int maxnm = 100000+1;
class node 
{
      
public:
             
int l,to;
             node 
* next;    
}
;
template
<class T>
class queue{
private:
    
long N;
    T
* s;
    
long beg,end;
public:
    inline 
void init(){
     beg
=end=0;
    }

    queue(
long size):N(size),s(new T[size]){
     init();
    }

    inline 
void push(const T& item){
     s[end]
=item;
     
++end;
     end
%=N;
    }

    inline T pop()
{
     T res
=s[beg];
     
++beg;
     beg
%=N;
     
return res;
    }

    inline 
bool empty(){
     
return beg==end;
    }

}
;

node 
*f[maxnm];
int n,m,s,t,ans;
int dist[maxn];
bool p[maxn];//判断点是否在队列当中
inline void init()
{
        FILE 
*fin = fopen("sssp.in","r");
        
int i,j,p1,p2,len;
        node 
*tp;
        fscanf(fin,
"%d%d",&n,&m);
        
for (i = 1 ; i <= m ; i++)
        
{
               fscanf(fin,
"%d%d%d",&p1,&p2,&len);
               tp 
= new node;
               tp 
-> l = len;
               tp 
-> to = p2; 
               tp 
-> next = f[p1];
               f[p1] 
= tp;                  
        }
    
        fscanf(fin,
"%d%d",&s,&t);   
}


inline 
void work()
{
         
int i,j,k;
         node 
* tp;
         queue 
<int> que(n+1);
         que.init();
         memset(dist,
126,sizeof(dist));
         dist[s] 
= 0;
         que.push(s);
         p[s] 
= true;
         
do 
         

              i 
= que.pop();
              tp 
= f[i];
              p[i] 
=    false;    //p[i] = false 表示i点不在队列当中
              while (tp!=NULL)
              
{
                 
if (dist[i]+tp->l<dist[tp->to])     
                    
{
                        dist[tp
->to] = dist[i]+tp->l;
                        
if (!p[tp->to])     //如果tp->to没有在队列当中,那就将它加进去
                        {
                           que.push(tp
->to);
                           p[tp
->to] = true;
                        }
 
                    }
      
                    tp 
= tp->next;
              }
         
         }
while (!que.empty());
       
}

inline 
void print()
{
        FILE 
*fout = fopen("sssp.out","w");
        fprintf(fout,
"%d\n",dist[t]);       
}

int main()
{
        init();
        work();
        print();
        
return 0;    
}



还有一种实现方法用了STL的queue,构图的方法很好是一个一维的加一个p数组
#include <iostream>
#include 
<queue>
using namespace std;

const long MAXN=10000;
const long lmax=0x7FFFFFFF;

typedef 
struct  
{
    
long v;
    
long next;
    
long cost;
}
Edge;


Edge e[MAXN];
long p[MAXN];
long Dis[MAXN];
bool vist[MAXN];

queue
<long> q;

long m,n;//点,边
void init()
{
    
long i;
    
long eid=0;

    memset(vist,
0,sizeof(vist));
    memset(p,
-1,sizeof(p));
    fill(Dis,Dis
+MAXN,lmax);

    
while (!q.empty())
    
{
        q.pop();
    }


    
for (i=0;i<n;++i)
    
{
        
long from,to,cost;
        scanf(
"%ld %ld %ld",&from,&to,&cost);

        e[eid].next
=p[from];
        e[eid].v
=to;
        e[eid].cost
=cost;
        p[from]
=eid++;

        
//以下适用于无向图
        swap(from,to);
        
        e[eid].next
=p[from];
        e[eid].v
=to;
        e[eid].cost
=cost;
        p[from]
=eid++;

    }

}


void print(long End)
{
    
//若为lmax 则不可达
    printf("%ld\n",Dis[End]);    
}


void SPF()
{

    init();

    
long Start,End;
    scanf(
"%ld %ld",&Start,&End);
    Dis[Start]
=0;
    vist[Start]
=true;
    q.push(Start);

    
while (!q.empty())
    
{
        
long t=q.front();
        q.pop();
        vist[t]
=false;
        
long j;
        
for (j=p[t];j!=-1;j=e[j].next)
        
{
            
long w=e[j].cost;
            
if (w+Dis[t]<Dis[e[j].v])
            
{
                Dis[e[j].v]
=w+Dis[t];
                
if (!vist[e[j].v])
                
{
                    vist[e[j].v]
=true;
                    q.push(e[j].v);
                }

            }

        }

    }


    print(End);

}


int main()
{
    
while (scanf("%ld %ld",&m,&n)!=EOF)
    
{
        SPF();
    }

    
return 0;
}
posted on 2008-09-11 17:01 Torres 阅读(1082) 评论(2)  编辑 收藏 引用 所属分类: Graph

评论

# re: SPFA (Shortest Path Faster Algorithm) 2009-03-26 19:29 xxx
静态与动态区别,能不能把原地址贴出来  回复  更多评论
  

# re: SPFA (Shortest Path Faster Algorithm) 2009-03-26 22:35 Torres
源地址倒是忘了,搜搜吧,这个应该容易理解的  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理