pku2240.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#include <math.h>
char Name[40][40];
char na[40], nb[40];
int N, M;
double path[40][40];

int GetID(char s[])
{
	int i;
	for (i = 0; i < N; i++)
	{
		if (strcmp(s, Name[i]) == 0)
		{
			return i;
		}
	}
}

int Solve()
{
	int i, j, k, s, e;
	double val;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		for (j = i + 1; j < N; j++)
		{
			path[i][j] = path[j][i] = 10000;
		}
		path[i][i] = 0;
	}
	for (i = 0; i < N; i++)
	{
		scanf("%s", Name[i]);
	}
	scanf("%d", &M);
	while (M--)
	{
		scanf("%s %lf %s", na, &val, nb);
		path[GetID(na)][GetID(nb)] = -log(val);
	}
	for (k = 0; k < N; k++)
	{
		for (i = 0; i < N; i++)
		{
			for (j = 0; j < N; j++)
			{
				if (path[i][j] > path[i][k] + path[k][j])
				{
					path[i][j] = path[i][k] + path[k][j];
				}
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		if (path[i][i] < 0)
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	int i = 0;
	while (scanf("%d", &N) != -1 && N)
	{
		printf("Case %d: ", ++i);
		if (Solve())
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
	return 0;
}