思路：设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算法判断是否存在负圈就行了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define Maxn 1100 6 #define inf 1<<30 7 using namespace std; 8 int dis[Maxn],vi[Maxn],n,index[Maxn],e; 9 struct Edge{ 10 int from,to,val,next; 11 }edge[Maxn*1000]; 12 void addedge(int from, int to, int val) 13 { 14 edge[e].from=from; 15 edge[e].to=to; 16 edge[e].val=val; 17 edge[e].next=index[from]; 18 index[from]=e++; 19 } 20 void init() 21 { 22 int i; 23 memset(index,-1,sizeof(index)); 24 memset(vi,0,sizeof(vi)); 25 for(i=0;i<Maxn;i++) 26 dis[i]=inf; 27 e=0; 28 } 29 int bellman_ford() 30 { 31 int i,j,temp,flag; 32 for(i=1;i<=n+1;i++) 33 { 34 flag=1; 35 for(j=0;j<e;j++) 36 { 37 temp=edge[j].from; 38 //cout<<edge[j].from<<" "<<edge[j].to<<" "<<edge[j].val<<" "<<j<<" "<<e<<endl; 39 if(dis[temp]+edge[j].val<dis[edge[j].to]) 40 { 41 dis[edge[j].to]=dis[temp]+edge[j].val; 42 flag=0; 43 } 44 } 45 if(flag) 46 return 1; 47 } 48 49 return 0; 50 } 51 int main() 52 { 53 int i,j,a,b,m,k; 54 char str[10]; 55 while(scanf("%d",&n)!=EOF,n) 56 { 57 scanf("%d",&m); 58 init(); 59 for(i=1;i<=m;i++) 60 { 61 scanf("%d%d%s%d",&a,&b,&str,&k); 62 if(str[0]=='g') 63 addedge(a+b+1,a,-k-1); 64 else 65 addedge(a,a+b+1,--k); 66 } 67 if(bellman_ford()) 68 printf("lamentable kingdom\n"); 69 else 70 printf("successful conspiracy\n"); 71 } 72 return 0; 73 }