Submission #287106

---

Source Code Expand

#include <iostream>
#include <algorithm>

using namespace std;

vector<int> j;
int d[101][101];

int main(){
	for(int i=0;i<101;++i){
		for(int k=0;k<101;k++){
			d[i][k] = 1000000;
		}
	}
	int n,x;
	int ans = 0;
	cin >> n >> x;
	for(int i = 1;i<=n;++i){
		int t;
		cin >> t;
		if(t==1)j.push_back(i);
	}
	for(int i=0;i<(n-1);++i){
		int a,b;
		cin >> a >> b;
		d[a][b] = 1;
		d[b][a] = 1;
	}
	for(int i=1;i<=n;++i){
		d[i][i]=0;
	}
	for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    int c = x;
    while(!j.empty()){
    	int mi,md=100000;
    	for(int to : j){
    		if(md > d[c][to]){
    			md = d[c][to];
    			mi = to;
    		}
    	}
    	ans += md;
    	c = mi;
    	j.erase(remove(j.begin(), j.end(), mi), j.end());
    }
    ans += d[c][x];
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result