QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#155514#2161. The Cost of Speed LimitsBazoka13ML 0ms0kbC++231.4kb2023-09-01 18:22:352023-09-01 18:22:36

Judging History

你现在查看的是最新测评结果

  • [2023-09-01 18:22:36]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-09-01 18:22:35]
  • 提交

answer

#include <bits/stdc++.h>
#define maxn 20086

using namespace std;

int n, c, m;
unsigned f[maxn][maxn];
vector<pair<int, int> > v[maxn]; 
vector<int> w;
int val[maxn];

void dfs(int i, int fa){
	for(auto it : v[i]){
		int to = it.first, co = it.second;
		if(to == fa) continue;
		val[to] = co;
		dfs(to, i);
	}
	unsigned sum = 0;
	for(auto it : v[i]){
		int to = it.first, co = it.second;
		if(to == fa) continue;
		unsigned mn = -1;
		for(int j = 0;j < m;j++) mn = min(mn, f[to][j]);
		sum += mn;
	}
	for(int j = val[i];j < m;j++){
		f[i][j] = 0;
		for(auto it : v[i]){
			int to = it.first;
			if(to == fa) continue;
			if(f[to][j] == -1){
				f[i][j] = -1;
				break;
			}
			f[i][j] += f[to][j];
		}
		f[i][j] = min(f[i][j], sum + c * (unsigned)v[i].size());
		if(i != 1) f[i][j] += w[j] - w[val[i]];
//		printf("%d %d %u--\n", i, j, f[i][j]);
	}
}

int main(){
	scanf("%d%d", &n, &c);
	for(int i = 1;i < n;i++){
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		v[x].push_back({y, z}), v[y].push_back({x, z});
		w.push_back(z);
	}
	sort(w.begin(), w.end());
	w.erase(unique(w.begin(), w.end()), w.end());
	m = w.size();
	for(int i = 1;i <= n;i++){
		for(auto &it : v[i]){
			it.second = lower_bound(w.begin(), w.end(), it.second) - w.begin();
		}
	}
	memset(f, -1, sizeof(f));
	dfs(1, 0);
	printf("%u", *min_element(f[1], f[1] + m));
}

详细

Test #1:

score: 0
Memory Limit Exceeded

input:

13 20
1 8 101
1 9 30
1 2 100
1 3 100
2 4 75
2 5 70
2 6 82
2 7 77
3 10 73
3 11 69
3 12 83
3 13 79

output:


result: