Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的程序,不知道错哪里了,老wa

Posted by goodpeter at 2007-08-27 13:26:39 on Problem 1935
#include <iostream>
using namespace std;

const int MAX = 999999;
int **city;
int n, k;
int a, b, d;
int i, j;
int num;
int m;
int *visit;
bool *arrived;
int best = MAX;

void search(int v, int sum, int number)
{
	if(number == 0)
	{
		if(best > sum)
		{
			best = sum;
		}
		return;
	}

	if(sum > best)
	{
		return;
	}

	int i;
	for(i = 1; i <= num; i++)
	{
		int temp = visit[i];
		if(!arrived[temp])
		{
			arrived[temp] = true;
			search(temp, sum + city[v][visit[i]], number - 1);
			arrived[temp] = false;
		}
	}
}

int main()
{
	while(cin>>n>>k)
	{
		city = new int*[n + 1];
		for(i = 0; i <= n; i++)
		{
			city[i] = new int[n + 1];
		}
		for(i = 1; i <= n; i++)
		{
			for(j = 1; j <= n; j++)
			{
				if(i == j)
				{
					city[i][j] = 0;
				}
				else
				{
					city[i][j] = MAX;
				}
			}
		}
		arrived = new bool[n + 1];
		memset(arrived, false, sizeof(arrived));
		for(i = 0; i < n - 1; i++)
		{
			cin>>a>>b>>d;
			city[a][b] = city[b][a] = d;
		}

		cin>>num;
		visit = new int[num + 1];
		for(i = 1; i <= num; i++)
		{
			cin>>visit[i];
		}

		int u, v, w;
		for(u = 1; u <= n; u++)
		{
			for(v = 1; v <= n; v++)
			{
				for(w = 1; w <= n; w++)
				{
					if(city[v][u] + city[u][w] < city[v][w])
					{
						city[v][w] = city[v][u] + city[u][w];
					}
				}
			}
		}

		arrived[k] = true;
		search(k, 0, num);

		cout<<best<<endl;

		delete [] visit;
		delete [] arrived;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator