poj 1364

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #define maxn 51000
 6 using namespace std;
 7 
 8 const int inf=1<<23;
 9 struct node
10 {
11     int u,v,c;
12     node(){}
13     node(int u,int v,int c):u(u),v(v),c(c){}
14 }p[maxn];
15 int head[maxn],next[maxn],cnt[maxn];
16 bool vis[maxn];
17 int e,n,m,top;
18 int dis[maxn];
19 
20 void addnode(int u,int v,int c)
21 {
22     p[e]=node(u,v,c);
23     next[e]=head[u];head[u]=e++;
24 }
25 
26 bool relax(int u,int v,int c)
27 {
28     if(dis[v]>dis[u]+c)
29     {
30         dis[v]=dis[u]+c;
31         return true;
32     }
33     return false;
34 }
35 
36 void inti()
37 {
38     memset(head,-1,sizeof(head));
39     memset(next,-1,sizeof(next));
40     e=0;
41     top=-1;
42     for(int i=0; i<m; i++)
43     {
44         int a,b,c;
45         char s[3];
46         scanf("%d %d %s %d",&a,&b,s,&c);
47         if(!strcmp(s,"gt")){
48             addnode(a+b,a-1,(-c-1));
49         }
50         else if(!strcmp(s,"lt")){
51             addnode(a-1,a+b,c-1);
52         }
53     }
54 }
55 int a[maxn];
56 bool spfa()
57 {
58     int i;
59     memset(cnt,0,sizeof(cnt));
60     for(i=0; i<=n+1; i++) {dis[i]=inf;vis[i]=0;}
61     for(i=0; i<n; i++)
62     {
63         a[++top]=i;
64         vis[i]=true;
65     }
66     dis[0]=0;
67     while(top>-1)
68     {
69         int pre=a[top--];
70         vis[pre]=false;
71         for(int i=head[pre]; i!=-1; i=next[i])
72         {
73             if(relax(pre,p[i].v,p[i].c)&&!vis[p[i].v])
74             {
75                 if((++cnt[p[i].v])>(n)) return false;
76                 a[++top]=p[i].v;
77                 vis[p[i].v]=true;
78             }
79         }
80     }
81     return true;
82 }
83 
84 int main()
85 {
86    while(scanf("%d",&n)&&n)
87    {
88        scanf("%d",&m);
89        inti();
90        if(spfa()) printf("lamentable kingdom
");
91        else printf("successful conspiracy
");
92    }
93    return 0;
94 }
View Code