2014
03-13

# City Planning

Recently Bob received a job. It’s to reform the city’s transport system. Since the city has so many villages, and the transportation network is so large that the government want to reduce the roads number. The government has just choose some of them, your duty is to build a transportation network between them to make them link with each other directly or indirectly. Meanwhile you should use the least money. You may suppose that the initial transportation network makes up a tree.

There are several test cases.
Each case starts with two integers n and m in a line. n stands for the number of all villages, m stands for the number of villages the government has chosen.( 0 < n < 1000, 0 < m <= n)
Then follow m integers in a line which means the chosen villages.
Then n – 1 lines follow, each line contains three integers a, b, c, indicating that between a and b there is a road available which costs c. (1 <= a, b <= n, a! = b, c <= 2000)

There are several test cases.
Each case starts with two integers n and m in a line. n stands for the number of all villages, m stands for the number of villages the government has chosen.( 0 < n < 1000, 0 < m <= n)
Then follow m integers in a line which means the chosen villages.
Then n – 1 lines follow, each line contains three integers a, b, c, indicating that between a and b there is a road available which costs c. (1 <= a, b <= n, a! = b, c <= 2000)

6 3
2 3 4
1 2 3
1 3 1
3 6 4
2 5 4
2 4 2

6

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn=2001;
struct node
{
int u,v,w,next;
} Edge[maxn];
{
}
void dfs(int u,int fa)
{
int i,j;
{
int v=Edge[i].v;
if(v==fa)continue;
dfs(v,u);
if(vis[v])
{
sum+=Edge[i].w;
vis[u]=1;
}

}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int i,j,a,b,c;
sum=NE=0;
memset(vis,0,sizeof(vis));
for(i=1; i<=m; i++)
{
scanf("%d",&root);
vis[root]=1;
}
for(i=1; i<n; i++)
{
scanf("%d%d%d",&a,&b,&c);
}
dfs(root,-1);
cout<<sum<<endl;
}
return 0;
}
/*
6 3
2 3 4
1 2 3
1 3 1
3 6 4
2 5 4
2 4 2
*/