3817737_ac_0ms_240k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int id[27];
double value[27];
vector <int> map[27];
int visited[27];

queue <int> que;

void bfs()
{
	while (!que.empty())
		que.pop();
	que.push(26);
	memset(visited, -1, sizeof(visited));
	visited[26] = 0;
	while (!que.empty())
	{
		int t = que.front();
		que.pop();
		for (int i = 0; i < map[t].size(); i++)
		{
			int u = map[t][i];
			if (visited[u] != -1)
				continue;
			visited[u] = visited[t] + 1;
			que.push(u);
		}
	}
}

void solve()
{
	int i;
	char p = '~';
	double best = -1;

	bfs();
	for (i = 0; i < 26; i++)
	{
		if (id[i] == 0)
			continue;
		double tmp = value[i] * pow(0.95, visited[i]);
		if (tmp > best)
		{
			best = tmp;
			p = i + 'A';
		}
	}
	printf("Import from %c\n", p);
}

int main()
{
	int i, j, k;
	char name[2];
	char str[28];

	while (scanf("%d", &n) == 1)
	{
		for (j = 0; j < 27; j++)
		{
			map[j].clear();
		}
		memset(id, 0, sizeof(id));
		while (n-- != 0)
		{
			scanf("%s", name);
			i = name[0] - 'A';
			id[i] = 1;
			scanf("%lf%s", &value[i], str);
			for (j = 0; str[j]; j++)
			{
				if (str[j] == '*')
				{
					k = 26;
					map[k].push_back(i);
				}
				else
					k = str[j] - 'A';
				map[i].push_back(k);
			}
		}
		solve();
	}
	return 0;
}