思路：设dis[i]为从0点到第i点的序列总和。那么对于A B gt k 来讲意思是dis[B+A]-dis[A]>k; 对于A B lt k来讲就是dis[B+A]-dis[A]<k;将两个不等式都化为
dis[A]-dis[B+A]<=-k-1; dis[A+B]-dis[A]<=k-1;那么就可以根据公式来建边了，用bellman_ford算法判断是否存在负圈就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Maxn 1100
#define inf 1<<30
using namespace std;
int dis[Maxn],vi[Maxn],n,index[Maxn],e;
struct Edge{
int from,to,val,next;
}edge[Maxn*];
void addedge(int from, int to, int val)
{
edge[e].from=from;
edge[e].to=to;
edge[e].val=val;
edge[e].next=index[from];
index[from]=e++;
}
void init()
{
int i;
memset(index,-,sizeof(index));
memset(vi,,sizeof(vi));
for(i=;i<Maxn;i++)
dis[i]=inf;
e=;
}
int bellman_ford()
{
int i,j,temp,flag;
for(i=;i<=n+;i++)
{
flag=;
for(j=;j<e;j++)
{
temp=edge[j].from;
//cout<<edge[j].from<<" "<<edge[j].to<<" "<<edge[j].val<<" "<<j<<" "<<e<<endl;
if(dis[temp]+edge[j].val<dis[edge[j].to])
{
dis[edge[j].to]=dis[temp]+edge[j].val;
flag=;
}
}
if(flag)
return ;
} return ;
}
int main()
{
int i,j,a,b,m,k;
char str[];
while(scanf("%d",&n)!=EOF,n)
{
scanf("%d",&m);
init();
for(i=;i<=m;i++)
{
scanf("%d%d%s%d",&a,&b,&str,&k);
if(str[]=='g')
addedge(a+b+,a,-k-);
else
addedge(a,a+b+,--k);
}
if(bellman_ford())
printf("lamentable kingdom\n");
else
printf("successful conspiracy\n");
}
return ;
}