比较纯的spfa

2009-05-12 10:44

#include<iostream>
using namespace std;

const int MAX = 1010;
const int INFI = 10000000;

struct Edge{
       int n;
       int adjvex[MAX];
       int weight[MAX];
       Edge(){
             n = 0;
       }
       void Add(int i,int v){
               adjvex[n] = i;
               weight[n++] = v;
            }
       }
}Graph[MAX];

int D[MAX],Dr[MAX];

int INC(int& tail){
    int t = tail;
    tail = (tail+1)%MAX;
    return t;
}

void SPFA(int s,int n);

int main(void){
    int n,m,s;
    int i,j,a,b,c;
    
    cin>>n>>m>>s;
    for(i=0;i<m;i++){
        cin>>a>>b>>c;
        Graph[a].Add(b,c);
    }
   
    SPFA(s,n);
    
    for(i=1;i<=n;i++){
        if(D[i]<INFI) cout<<D[i]<<endl;
        else cout<<"No Path\n";
    }

    system("pause");
    return 0;
}


void SPFA(int s,int n){
     int Q[MAX],head,tail;
     int i,j,t,u,v,w,time[MAX];
     bool inQ[MAX];
    
     //Init

     head = tail = 0;
    
     for(i=1;i<=n;i++)
         D[i] = INFI;
     D[s] = 0;
    
     memset(inQ,0,sizeof(inQ) );
     inQ[s] = true;
     Q[INC(tail) ] = s;
    
     //body

     while(head!=tail){
           u = Q[INC(head) ];
           inQ[u] = false;
          
           for(i=0;i<Graph[u].n;i++){
               v = Graph[u].adjvex[i];
               w = Graph[u].weight[i];
              
               if(D[v] > D[u]+w){
                  D[v] = D[u]+w;
                  if(!inQ[v]){
                     inQ[v] = true;
                     Q[INC(tail) ] = v;
                  }
               }
           }
     }
}