提出 #485252

---

ソースコード 拡げる

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<utility>
#define N 2010
using namespace std;
struct edge{
	edge(int _to,int _w):to(_to),w(_w){}
	int to;
	int w;
};
priority_queue<pair<int,int> > bpq;
vector<edge> g[N];
vector<int> leaf[N];
int dep[N],par[N],sz[N],now[N],c[N];
long long add[N][N];
bool vis[N],del[N];
bool cmp(int i,int j){
	return dep[i]<dep[j];
}
void build(int u,int pre){
	dep[u]=pre;
	vis[u]=true;
	int cnt=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].to;
		if(vis[v]) continue;
		par[v]=u;
		build(v,pre+g[u][i].w);
		leaf[u].push_back(leaf[v].back());
		cnt++;
	}
	if(!cnt) leaf[u].push_back(u);
	else sort(leaf[u].begin(),leaf[u].end(),cmp);
}
void fix(int u){
	while(par[u]&&!del[u]){
		int p=par[u];
		del[u]=true;
		leaf[p].pop_back();
		if(!leaf[p].empty()) bpq.push(make_pair(dep[leaf[p].back()]-dep[p],leaf[p].back()));
		u=p;
	}
}
void solve1(int u){
	memset(vis,0,sizeof(vis));
	memset(del,0,sizeof(del));
	par[u]=0;
	build(u,0);
	int mx=leaf[u].back();
	bpq.push(make_pair(dep[mx],mx));
	while(!bpq.empty()){
		add[u][sz[u]++]=1LL*bpq.top().first*c[u];
		int tmp=bpq.top().second;
		bpq.pop();		
		fix(tmp);
	}
}
long long solve2(int n,int m){
	long long res=0;
	priority_queue<pair<long long,int> > pq;
	for(int i=1;i<=n;i++){
		if(now[i]<sz[i]) pq.push(make_pair(add[i][0],i)),now[i]++;
	}
	while(!pq.empty()&&m){
		res+=pq.top().first;
		int u=pq.top().second;
		pq.pop();
		if(now[u]<sz[u]){
			pq.push(make_pair(add[u][now[u]++],u));
		}
		m--;
	}
	return res;
}
int main(){
	int n,m,x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		g[x].push_back(edge(y,z));
		g[y].push_back(edge(x,z));
	}
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<=n;i++) solve1(i);
	printf("%lld\n",solve2(n,m));
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:80:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
./Main.cpp:82:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&y,&z);
                           ^
./Main.cpp:86:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&c[i]);
                                         ^

ジャッジ結果