#include <iostream>
#include <vector>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define pb push_back
const int maxN = 100'000;
ll INF = 2'000'000'001;
vector<pair<int, ll>> edge[1+maxN];
vll S(1+maxN), V(1+maxN);
vi P(1+maxN);
vll D(1+maxN, 0);
vi ord;
void dfs(int u, int p)
{
ord.push_back(u);
P[u] = p;
for(auto x: edge[u])
{
int v = x.first;
ll d = x.second;
if(v == p) continue;
D[v] = D[u] + d;
dfs(v, u);
}
}
int main()
{
int N;
cin >> N;
for(int i = 1; i <= N-1; i++)
{
int u, v;
ll d;
cin >> u >> v >> d;
edge[u].pb({v, d});
edge[v].pb({u, d});
}
for(int i = 2; i <= N; i++) cin >> S[i] >> V[i];
dfs(1, 1);
vll dp(1+N, INF);
dp[1] = 0;
for(int u: ord)
{
for(int v = P[u]; 1; v = P[v])
{
dp[u] = min(dp[u], S[u] + V[u]*D[u] + (-D[v] * V[u] + dp[v]));
if(v == 1) break;
}
}
for(int i = 2; i <= N; i++) cout << dp[i] << ' ';
cout << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5324 KB |
Output is correct |
2 |
Correct |
20 ms |
5868 KB |
Output is correct |
3 |
Execution timed out |
1062 ms |
11264 KB |
Time limit exceeded |
4 |
Execution timed out |
1058 ms |
13764 KB |
Time limit exceeded |
5 |
Execution timed out |
1092 ms |
16576 KB |
Time limit exceeded |
6 |
Execution timed out |
1082 ms |
19036 KB |
Time limit exceeded |
7 |
Execution timed out |
1092 ms |
12696 KB |
Time limit exceeded |
8 |
Execution timed out |
1057 ms |
16156 KB |
Time limit exceeded |
9 |
Execution timed out |
1064 ms |
16948 KB |
Time limit exceeded |
10 |
Execution timed out |
1088 ms |
16000 KB |
Time limit exceeded |