QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#155514 | #2161. The Cost of Speed Limits | Bazoka13 | ML | 0ms | 0kb | C++23 | 1.4kb | 2023-09-01 18:22:35 | 2023-09-01 18:22:36 |
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