poj3259 SPFA

学习SPFA，正好是裸的SPFA，然后我就学习了一下。
  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <math.h>
  4 #include <queue>
  5 #include <string.h>
  6 #define  maxn 600
  7 #define  INF 0x7fffffff
  8 using namespace std;
  9 struct node {
 10     int to;
 11     int weight;
 12     node* next;
 13 };
 14 node* LIST[maxn];
 15 queue<int>Q;
 16 int dist[maxn],inq[maxn],count1[maxn],path[maxn];
 17 bool SPFA(int begin,int n);
 18 int main()
 19 {
 20     int n,m,w;
 21     int i,j;
 22     int t;
 23     int t1,t2,t3;
 24     node* temp;
 25     while(~scanf("%d",&t)){
 26         while(t--){
 27            scanf("%d%d%d",&n,&m,&w);
 28            memset(LIST,0,sizeof(LIST));
 29            while(m--){
 30                scanf("%d%d%d",&t1,&t2,&t3);
 31                temp=new node;
 32                temp->to=t2;  temp->weight=t3; temp->next=NULL;
 33                if(LIST[t1]==NULL)
 34                    LIST[t1]=temp;
 35                else
 36                    temp->next=LIST[t1],LIST[t1]=temp;
 37                temp=new node;
 38                temp->to=t1;  temp->weight=t3; temp->next=NULL;
 39                if(LIST[t2]==NULL)
 40                    LIST[t2]=temp;
 41                else
 42                    temp->next=LIST[t2],LIST[t2]=temp;
 43            } 
 44            while(w--){
 45                scanf("%d%d%d",&t1,&t2,&t3);
 46                temp=new node;
 47                temp->to=t2; temp->weight=-t3; temp->next=NULL;
 48                if(LIST[t1]==NULL)
 49                    LIST[t1]=temp;
 50                else
 51                    temp->next=LIST[t1],LIST[t1]=temp;
 52            }
 53 
 54            if(SPFA(1,n))
 55                printf("YES\n");
 56            else
 57                printf("NO\n");
 58            for(i=1;i<=n;++i){
 59                temp=LIST[i];
 60                while(temp!=NULL){
 61                    LIST[i]=temp->next;  delete temp; temp=LIST[i];
 62                }
 63            }
 64         }
 65     }
 66     return 0;
 67 }
 68 bool SPFA(int begin,int n)
 69 {
 70     memset(inq,0,sizeof(inq));
 71     memset(count1,0,sizeof(count1));
 72     while(!Q.empty())
 73         Q.pop();
 74     int i,u;
 75     for(i=1;i<=n;++i)
 76         dist[i]=INF,path[i]=begin,inq[i]=0;
 77     node* temp;
 78     dist[begin]=0,inq[begin]++;
 79     Q.push(begin),count1[begin]++;
 80     while(!Q.empty()){
 81         u=Q.front();
 82         Q.pop();
 83         inq[u]--;
 84         if(count1[u]>n)
 85            return true;
 86         temp=LIST[u];
 87         while(temp!=NULL){
 88             int v=temp->to;
 89             if(dist[v]>dist[u]+temp->weight){
 90                 dist[v]=dist[u]+temp->weight,path[v]=u;
 91                 if(!inq[v]){
 92                       Q.push(v);  count1[v]++;  inq[v]++;
 93                 }
 94             }
 95             temp=temp->next;
 96         }
 97     }
 98     return false;
 99 }
100 
101 
102 
103 
104     
105     
106