比赛 20110725 评测结果 AAAAAAAAAAAAAAAATTTT
题目名称 存在与否 最终得分 80
用户昵称 201101 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-25 12:24:51
显示代码纯文本
#include <fstream>
using namespace std;

int N,minleng=1000000000,map[1001][1001][2],way[1001];/*As for map[x][y][z] : when z = "0" it means the city to go; when z = "1" it means the distance to the city*/
bool unava[1001][1001],walked[10001];

bool checkit(void)
{
	int i;
	for (i=1;i<=N;i++)
		if (!walked[i])
			return(false);
	return(true);
}

void tryit(int nowpos,int nowleng)
{
	if (nowleng>=minleng)
		return;
	if (nowpos!=0)
		walked[nowpos]=true;
	if (nowpos==0&&nowleng!=0&&checkit())
		minleng=nowleng;
	else
	{
		int i;
		for (i=1;i<=way[nowpos];i++)
		{
			if (!unava[nowpos][i]&&!walked[map[nowpos][i][0]])
			{
				unava[nowpos][i]=true;
				tryit(map[nowpos][i][0],nowleng+map[nowpos][i][1]);
				unava[nowpos][i]=false;
			}
		}
	}
	if (nowpos!=0)
		walked[nowpos]=false;
}

int main(void)
{
	ifstream input("exists.in");
	ofstream output("exists.out");
	int i,M,x,y;
	input>>N;
	for (i=1;i<=N-1;i++)
	{
		input>>x>>y;
		way[x]++;
		way[y]++;
		map[x][way[x]][0]=y;
		map[y][way[y]][0]=x;
		input>>map[x][way[x]][1];
		map[y][way[y]][1]=map[x][way[x]][1];
	}
	input>>M;
	for (i=1;i<=M+1;i++)
	{
		input>>x>>y;
		way[x]++;
		way[y]++;
		map[x][way[x]][0]=y;
		map[y][way[y]][0]=x;
		input>>map[x][way[x]][1];
		map[y][way[y]][1]=map[x][way[x]][1];
	}
	tryit(0,0);
	if (minleng==1000000000)
		output<<"-1\n";
	else
		output<<minleng<<endl;
	input.close();
	output.close();
	return(0);
}