poj1364 King

典型的差分约束的题目。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#define MAXD 110
using namespace std;
int N,M,graph[MAXD][MAXD],dis[MAXD];
bool vis[MAXD][MAXD];

int bellman()
{
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    int k,i,j;
    int num=N+1;
    for(k=1;k<=num;k++)
    {
        for(i=0;i<=num;i++)
        {
            for(j=0;j<=num;j++)
            {
                if(vis[i][j]&&dis[j]>dis[i]+graph[i][j])
                dis[j]=dis[i]+graph[i][j];
            }
        }
    }
    for(i=0;i<=num;i++)
    {
        for(j=0;j<=num;j++)
        {
            if(vis[i][j]&&dis[j]>dis[i]+graph[i][j])
            return 0;
        }
    }
    return 1;
}
int main()
{
    //freopen("test.txt","r",stdin);
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        if(N==0)
        return 0;
        int i,j;
        memset(graph,-1,sizeof(graph));
        memset(vis,0,sizeof(vis));
        int si,ni,ki;
        char oi[2];
        for(i=1;i<=M;i++)
        {
            scanf("%d%d%s%d",&si,&ni,oi,&ki);
            if(oi[0]=='g')
            {
                graph[si+ni+1][si]=(ki+1)*(-1);
                vis[si+ni+1][si]=true;
            }
            else
            {
                graph[si][si+ni+1]=ki-1;
                vis[si][si+ni+1]=true;
            }
        }
        for(i=0;i<=N;i++)
        {
            if(!vis[0][i+1])
            {
                graph[0][i+1]=0;
                vis[0][i+1]=true;
            }
        }
        if(bellman())
        printf("lamentable kingdom\n");
        else
        printf("successful conspiracy\n");
    }
    return 0;
}