Submission #968814

---

Source Code Expand

// jissou, muri!











#include <bits/stdc++.h>
using namespace std;

struct Edge{
	long long a,b,c,d;
};
vector<Edge> g[100010];

void solve(long long N, long long X, vector<long long> A, vector<long long> B, vector<long long> C){
	if( N == 2 ){
		cout << C[0] << endl;
		return;
	}
	for(int i = 0 ; i < N ; i++){
		--A[i],--B[i];
		g[A[i]].push_back({A[i],B[i],C[i]});
		g[B[i]].push_back({B[i],A[i],C[i]});
	}
	long long ans1 = 0;
	long long ans2 = 0;
	for(int i = 0 ; i < N ; i++){
		vector<int> cst;
		cst.push_back(X);
		for( auto e : g[i] ){
			cst.push_back(e.c);
		}
		sort(cst.begin(),cst.end());
		long long sm = 0;
		for( auto &&e : g[i] ){
			int cost = min(e.c,cst[e.c==cst[0]] + X);
			e.c = cost;
			ans1 += cost;
			e.d = min<int>(X,cost);
			sm += e.d;
		}
		long long w = 0;
		for( auto &&e : g[i] ){
			w += (sm-e.d) + e.c * (g[i].size() - 1);
			cout << i + 1 << " " << (sm-e.d) + e.c * (g[i].size() - 1) << endl;
		}
		ans2 += w;
	}
	ans1 /= 2;
	ans2 /= 2;
	cout << ans1 << " " << ans2 <<  endl;
	
}



int main(){	
	ios::sync_with_stdio(false);
	long long N;
	long long X;
	cin >> N;
	vector<long long> A((N-1)-1+1);
	vector<long long> C((N-1)-1+1);
	vector<long long> B((N-1)-1+1);
	cin >> X;
	for(int i = 0 ; i <= (N-1)-1 ; i++){
		cin >> A[i];
		cin >> B[i];
		cin >> C[i];
	}
	solve(N, X, A, B, C);
	return 0;
}

Submission Info

Judge Result