1130.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1130 on 2005-11-06 at 19:18:41 */ 
#include <cstdio>
#include <cstring>
#include <cmath>

const int MAX = 32;
const double FEE = 0.95;
const double eps = 1e-8;

class Planet {
public:
	int link[MAX];
	int n;
	double good;
};

Planet p[MAX];
int galaxy[MAX], n;
int stack[MAX], top;

char Dijkstra();

int main()
{
	char path[MAX], o;
	int i, j, x;
	double d;
	
	while(scanf("%d", &n) == 1) {
		top = 0;
		for(i = 0; i < n; i++) {
			scanf("%*['\n']%c %lf %s", &o, &d, path);
			x = o - 'A';
			galaxy[i] = x;
			p[x].good = d;
			p[x].n = 0;
			for(j = 0; path[j] != '\0'; j++) {
				if(path[j] == '*') {
					stack[top++] = x;
				} else if(path[j] >= 'A' && path[j] <= 'Z') {
					p[x].link[p[x].n++] = path[j] - 'A';
				}
			}
		}
		printf("Import from %c\n", Dijkstra());
	}
	
	return 0;
}

char Dijkstra()
{
	char o;
	int d[MAX], i, j, q;
	int min, mini;
	double r, max;
	bool visit[MAX] = {false};
	
	for(i = 0; i < n; i++) {
		d[galaxy[i]] = MAX;
	}
	for(i = 0; i < top; i++) {
		d[stack[i]] = 0;
	}
	max = 0;
	for(i = 0; i < n; i++) {
		min = MAX;
		mini = -1;
		for(j = 0; j < n; j++) {
			if(!visit[galaxy[j]] && d[galaxy[j]] < min) {
				min = d[galaxy[j]];
				mini = galaxy[j];
			}
		}
		if(mini == -1) {
			break;
		} else {
			visit[mini] = true;
			r = p[mini].good;
			for(j = 0; j < d[mini]; j++) {
				r *= FEE;
			}
			if(r - max > eps) {
				max = r;
				o = mini + 'A';
			} else if(fabs(r-max) < eps) {
				if(o > mini + 'A') {
					o = mini + 'A';
				}
			}
			for(j = 0; j < p[mini].n; j++) {
				q = p[mini].link[j];
				if(!visit[q] && d[q] > d[mini] + 1) {
					d[q] = d[mini] + 1;
				}
			}
		}
	}
	
	return o;
}