| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我的程序,不知道错哪里了,老wa#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator