Pagini recente » Cod sursa (job #1860995) | Cod sursa (job #1397503) | Cod sursa (job #1793465) | Cod sursa (job #1423052) | Cod sursa (job #1609323)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("subarbore.in");
ofstream g("subarbore.out");
int n,m,t,suma,minim=200000000;
bool S[41],T[41];
vector<int> C(41,0);
vector<int> C1(41,0);
vector < pair < int,int > > M[41];
vector <int> Ns(10);
struct Muchie{
int x,y,c;
};
vector <Muchie> G;
void APM(){
for(int i=0;i<m;i++){
if(S[G[i].x] && S[G[i].y]){
if(C[G[i].x] != C[G[i].y]){
int minim=min(C[G[i].x],C[G[i].y]),maxim=max(C[G[i].x],C[G[i].y]);
suma+=G[i].c;
replace(C.begin(),C.end(),maxim,minim);
}
}
}
}
bool comp1(const Muchie & a ,const Muchie & b){
return a.c<b.c;
}
void back(int k){
int nod=NS[k];
for(n==k){
APM();
}else{
for(vector<int>::iterator it=M[nod].begin();it!=M[nod].end();it++){
if(C[nod]!=C[(*it).first]){
int minim=min(C[nod],C[(*it).first]),maxim=max(C[nod],C[(*it).first]);
suma+=(*it).second;
C[(*it).first]
back(k+1);
suma-=(*it).second;
}
}
}
}
int main()
{
int x,y,c;
f>>n>>m;
for(int i=0;i<m;i++){
f>>x>>y>>c;
Muchie m;
m.x=x;
m.y=y;
m.c=c;
G.push_back(m);
M[x].push_back(make_pair(y,c));
M[y].push_back(make_pair(x,c));
}
f>>t;
for(int i=1;i<=n;i++){
T[x]=false;
}
for(int i=0;i<t;i++){
f>>x;
NS.push_back(x);
T[x]=true;
S[x]=true;
}
for(int i=1;i<=n;i++){
C1[i]=i;
}
C=C1;
sort(G.begin(),G.end(),comp1);
back(1);
g<<minim;
return 0;
}