模板题，一直想用SPFA来做，可是这题却遇到了麻烦。因为对于原来的题来说一直想弄懂那个超级原点是怎么做的。这次用SPFA弄了N久，还是没弄出来... 后来果断用了BellmanFord()裸A啊....
原来Bellman比SPFA还要好写，果断不用Dijstra了~
#include<iostream>
#include<queue>
#define MAXN 103
#define INF 0x7F7F7F7F
using namespace std;
/*
struct Node
{int v,price;Node *next;
}Edge[MAXN],*ptr[MAXN];
*/
struct Node
{int u,v,price;
}Edge[MAXN];int N,M;
int edgeNum;void addEdge( int u,int v,int val )
{Edge[edgeNum].u=u;Edge[edgeNum].v=v;Edge[edgeNum].price=val;edgeNum++;/*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];int cnt[MAXN];queue<int>myQueue;memset( used,1,sizeof(used) );memset( dist,0x7F,sizeof(dist) );memset( cnt,0,sizeof(cnt) );while( !myQueue.empty() )myQueue.pop();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];if( dist[u]==INF ) dist[u]=0;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-1 )return false;}}p=p->next;}}return true;
}*/bool Bellman_Ford()
{int dist[MAXN];int i,j;memset( dist,0,sizeof(dist) );for( i=0;i<=N;i++ )for( j=0;j<M;j++ )if( dist[Edge[j].v]>dist[Edge[j].u]+Edge[j].price )dist[Edge[j].v]=dist[Edge[j].u]+Edge[j].price;for( j=0;j<M;j++ )if( dist[Edge[j].v]>dist[Edge[j].u]+Edge[j].price )return false;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 );}/*for( i=1;i<=M;i++ ){Node *p=&Edge[edgeNum++];p->v=i;p->price=0;p->next=ptr[0];ptr[0]=p;}*///if( spfa() )if( !Bellman_Ford() )printf( "successful conspiracy\n" );elseprintf( "lamentable kingdom\n" ); }return 0;
}