king(差分约束).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>

int n,m;
int si,ni,ki;
char oi[5];
int dist[110];
struct node {
    int s,e,v;
}edge[110];

bool bellman_ford()
{
    int i,j;
    bool flag;
	
    memset(dist,0x7f,sizeof(dist));
    dist[0] = 0;
    for (i=0;i<=n;i++) {
        flag = true;
        for (j=0;j<m;j++) {
            if (dist[edge[j].s]+edge[j].v < dist[edge[j].e]) {
                dist[edge[j].e] = dist[edge[j].s] + edge[j].v;
                flag = false;
            }
        }
        if (flag) {
            break ;
        }
    }
    return flag;
}

int main()
{
    int i,j;
    while (scanf("%d",&n), n) {
        scanf("%d",&m);
        for (i=0;i<m;i++) {
            scanf("%d %d %s %d",&si,&ni,oi,&ki);
            if (oi[0] == 'g') {
                edge[i].s = si+ni;
                edge[i].e = si-1;
                edge[i].v = -ki-1;
            }
            else {
                edge[i].s = si-1;
                edge[i].e = si+ni;
                edge[i].v = ki-1;
            }
        }//m
        if (bellman_ford()) {
            printf("lamentable kingdom\n");
        }
        else {
            printf("successful conspiracy\n");
        }
    }
}