POJ 1364 King 差分约束 SPFA

终于用SPFA AC了~~这题还真是！！稍后要把差分约束和SPFA总结一下~~，觉得这题还是挺有意思的。具体为什么WA了呢？？？ 不是那么清楚~~ 照着做就是AC了。发现形成链表就那么简单~ 嘿嘿~

#include<iostream>
#include<queue>
#define MAXN 103
#define INF 0x7F7F7F7F
using namespace std;struct Node
{int v,price;Node *next;
}Edge[MAXN],*ptr[MAXN];int N,M;
int edgeNum;void addEdge( int u,int v,int val )
{Node *p=&Edge[edgeNum++];p->v=v;p->price=val;p->next=ptr[u];ptr[u]=p;
}bool spfa()
{bool used[MAXN];int dist[MAXN],cnt[MAXN];queue<int>myQueue;memset( used,true,sizeof(used) );memset( dist,0,sizeof(dist) );memset( cnt,0,sizeof(cnt) );for( int i=0;i<=N;i++ ) myQueue.push(i);while( !myQueue.empty() ){int u=myQueue.front();myQueue.pop();used[u]=false;Node *p=ptr[u];while( p ){if( dist[p->v]>dist[u]+p->price ){dist[p->v]=dist[u]+p->price;if( !used[p->v] ){myQueue.push(p->v);used[p->v]=true;if( ++cnt[p->v]>N )return false;}}p=p->next;}}return true;
}int main()
{while( scanf( "%d",&N )!=EOF ){edgeNum=0;if( N==0 )break;scanf( "%d",&M );int i,j,k;char com[3];int a,b,p;for( i=0;i<=N;i++ ) ptr[i]=NULL;for( i=1;i<=M;i++ ){scanf( "%d %d %s %d",&a,&b,&com,&p );if( com[0]=='g' )addEdge( a+b,a-1,-p-1 );elseaddEdge( a-1,a+b,p-1 );}if( !spfa() )printf( "successful conspiracy\n" );elseprintf( "lamentable kingdom\n" ); }return 0;
}