Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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:

User ID:
Title:

Content: