4282046_wa.cpp

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

#include <queue>
#include <set>
#include <vector>
#include <string>
#include <stdio.h>
#include <algorithm>

using namespace std;

struct node
{
	string a, b;
	int d;
}r[100];

struct Node
{
	int ed;
	int fa;
	int d;

	Node()
	{

	}

	Node (int a, int b, int c)
	{
		ed = a;
		fa = b;
		d = c;
	}
};

set <string> s;
vector <Node> shit[100];
int cnt;
vector < string > cao;
int n;

int find(string a)
{
	int i, j, k;

	i = 0;j = cao.size();
	while (i != j)
	{
		k = (i + j) / 2;
		if (a == cao[k])
		{
			return k;
		}
		if (a.compare(cao[k]) < 0)
		{
			j = k;
		}
		else
		{
			i = k + 1;
		}
	}
	return 0;
}

int st;
int clear[100];

bool cmp(int a, int b)
{
	if (clear[a] != clear[b])
	{
		return clear[a] > clear[b];
	}
	return cao[a].compare(cao[b]) < 0;
}

void bfs()
{
	memset(clear, -1, sizeof clear);
	queue <int> q;
	clear[st] = 100;
	q.push(st);
	while (!q.empty())
	{
		int t = q.front();
		q.pop();

		for (int i = 0; i < shit[t].size(); i++)
		{
			Node vv = shit[t][i];
			if (clear[vv.ed] != -1)
			{
				continue;
			}
			if (vv.fa == 1)
			{
				clear[vv.ed] = clear[t] - vv.d;
			}
			else
			{
				clear[vv.ed] = clear[t] + vv.d;
			}
			q.push(vv.ed);
		}
	}
	int index[100];

	int i;

	for (i = 0; i < n; i++)
	{
		index[i] = i;
	}
	sort(index, index + n, cmp);
	for (i = 0; i < n; i++)
	{
		if (cao[index[i]] == "Ted")
		{
			continue;
		}
		printf("%s %d\n", cao[index[i]].c_str(), clear[index[i]]);
	}
}

void init()
{
	int i;

	cao.clear();
	cnt = 0;
	for (set<string>::iterator it = s.begin(); it != s.end(); ++it)
	{
		cao.push_back(*it);
	}
	for (i = 0; i < n; i++)
	{
		int ida = find(string(r[i].a));
		int idb = find(string(r[i].b));

		shit[ida].push_back(Node(idb, 1, r[i].d));
		shit[idb].push_back(Node(ida, 0, r[i].d));
		if (r[i].a == "Ted")
		{
			st = ida;
		}
	}
	bfs();
}

int main()
{
	int cas;
	int i, j;
	char a[100], b[100];

	scanf("%d", &cas);

	for (i = 1; i <= cas; i++)
	{
		printf("DATASET %d\n", i);
		scanf("%d", &n);
		s.clear();
		for (j = 0; j < n; j++)
		{
			scanf("%s%s%d", a, b, &r[j].d);
			r[j].a = string(a);
			r[j].b = string(b);
			s.insert(r[j].a);
			s.insert(r[j].b);
			shit[j].clear();
		}
		init();
	}
	return 0;
}