#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <functional>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;
#define ALL(x) x.begin(), x.end()
int n, prep[1<<19], vel[1<<19];
vector<pair<int, int>> g[1<<19];
/*
* dp[i] = cost from i to 1
*
* dp[i] = min p (dp[p] + distance(i, p) + start[i])
*
*/
int sub1()
{
const int N = 2586;
ll dp[N]{0}, tin[N], tout[N], timer = 1, rd[N];
function<void(int, int, int)> dfs = [&](int u, int p, ll d) {
tin[u] = timer++;
rd[u] = d;
for (auto [w, v] : g[u]) if (v != p) dfs(v, u, d+w);
tout[u] = timer - 1;
};
dfs(1, 1, 0);
memset(dp, 63, sizeof dp);
dp[1] = 0;
function<void(int, int)> dfs1 = [&](int u, int p) {
for (int a = 1; a <= n; ++a)
if (tin[a] <= tin[u] && tout[u] <= tout[a]) dp[u] = min(dp[u], dp[a] + prep[u] + vel[u] * (rd[u] - rd[a]));
for (auto [w, v] : g[u]) if (v != p) dfs1(v, u);
};
dfs1(1, 1);
for (int i = 2; i <= n; ++i) printf("%lld ", dp[i]);
return 0;
}
int main()
{
scanf("%d", &n);
for (int u, v, w, i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), g[u].emplace_back(w, v), g[v].emplace_back(w, u);
for (int i = 2; i <= n; ++i) scanf("%d%d", prep+i, vel+i);
if (n <= 2500) return sub1();
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
harbingers.cpp:54:47: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | for (int u, v, w, i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), g[u].emplace_back(w, v), g[v].emplace_back(w, u);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:55:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | for (int i = 2; i <= n; ++i) scanf("%d%d", prep+i, vel+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
16 ms |
15468 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
17500 KB |
Output isn't correct |
| 4 |
Incorrect |
38 ms |
18556 KB |
Output isn't correct |
| 5 |
Incorrect |
37 ms |
19592 KB |
Output isn't correct |
| 6 |
Incorrect |
45 ms |
20624 KB |
Output isn't correct |
| 7 |
Incorrect |
32 ms |
19036 KB |
Output isn't correct |
| 8 |
Incorrect |
49 ms |
20940 KB |
Output isn't correct |
| 9 |
Incorrect |
44 ms |
21076 KB |
Output isn't correct |
| 10 |
Incorrect |
49 ms |
20940 KB |
Output isn't correct |
