제출 #885774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
885774		peterandvoi	Harbingers (CEOI09_harbingers)	C++17	20 / 100	10 ms	920 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define db(...) " [" << #__VA_ARGS__ << " : " << (__VA_ARGS__) << "] "

const int N = 2505;

int n;
int d[N], s[N], c[N], tin[N], tout[N];
vector<pair<int, int>> g[N];
int dp[N];

int order;

void dfs(int u = 1) {
  tin[u] = ++order;
  for (auto [v, w] : g[u]) {
    if (!tin[v]) {
      d[v] = d[u] + w;
      dfs(v);
    }
  }
  tout[u] = order;
}

bool is_ancs(int a, int b) {
  return tin[a] <= tin[b] && tin[b] <= tout[a];
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1, u, v, w; i < n; ++i) {
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  for (int i = 2; i <= n; ++i) {
    cin >> s[i] >> c[i];
  }
  dfs();
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 1);
  sort(ord.begin(), ord.end(), [&](int i, int j) { 
    return d[i] < d[j];
  });
  for (int i = 1; i < n; ++i) {
    int u = ord[i];
    dp[u] = 1e18;
    for (int v = 1; v <= n; ++v) {
      if (is_ancs(v, u)) {
        dp[u] = min(dp[u], dp[v] + (d[u] - d[v]) * c[u] + s[u]);
      }
    }
  }
  for (int i = 2; i <= n; ++i) {
    cout << dp[i] << " ";
  }
}

// brute for stress

• Subtask 1: 20 / 100