1068.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1068 on 2006-07-28 at 10:36:01 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int MAX = 128;
const int INF = 200000000;
 
class Edge {
public:
	int s, t, w;
	void make();
};
void Edge::make() {
	int a, b;
	char order[4];
	scanf("%d %d %s %d", &a, &b, order, &w);
	b += a; a--;
	if(!strcmp(order, "gt")) s = b, t = a, w = -w;
	else s = a, t = b;
	w--;
}
 
class Graph {
private:
	Edge edge[MAX];
	int n, en;
public:
	void make(int, int);
	bool bellman_ford();
};
void Graph::make(int noden, int m) {
	int i;
	n = noden+1, en = m;
	for(i = 0; i < m; i++) edge[i].make();
}
bool Graph::bellman_ford() {
	int i, j;
	int d[MAX] = { 0 };
	for(i = 1; i < n; i++) d[i] = INF;
	for(i = 0; i < en; i++) {
		if(edge[i].s == 0) d[edge[i].t] = min(d[edge[i].t], edge[i].w);
	}
	bool ex = true;
	for(i = 0; i <= n+1 && ex; i++) {
		ex = false;
		for(j = 0; j < en; j++) {
			if(d[edge[j].s] + edge[j].w < d[edge[j].t]) {
				if(i == n+1) return false;
				else {
					d[edge[j].t] = d[edge[j].s] + edge[j].w;
					ex = true;
				}
			}
		}
	}
	return true;
}
 
int main()
{
	Graph g;
	int n, m;
	
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		g.make(n, m);
		if(g.bellman_ford()) printf("lamentable kingdom\n");
		else printf("successful conspiracy\n");
	}
	
	return 0;
}