Submission #478317

#	Time	Username	Problem	Language	Result	Execution time	Memory
478317		vitkute	Harbingers (CEOI09_harbingers)	C++11	20 / 100	1096 ms	11920 KiB

harbingers

/// [_DukkSooCee3305_]
/// Date : 05/10/2021
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define ALL(i_) i_.begin(), i_.end()
#define Random(lf_, rt_) (lf_ + rand() % (rt_ - lf_ + 1))
#define PB push_back
#define sz(i_) ((int)(i_).size())
#define reset(i_, x_) memset(i_, x_, sizeof i_)
#define TASK "HARBINGERS"

typedef long long ll;
typedef long double ld;
typedef pair<int, ll> ii;

const int oo = 1000000099;
const int mod = 1000000007;
const int maxn = 100011;

int n;
vector<ii> ke[maxn];
ll s[maxn], v[maxn], dp[maxn], d[maxn];
bool vs[maxn];

namespace process{

    void DFS(int u, int par){
        if(u > 1){
            dp[u] = oo;
            FOR(p, 1, n){
                if(!vs[p]) continue;
                dp[u] = min(dp[u], dp[p] + s[u] + v[u] * (d[u] - d[p]));
            }
        }
        vs[u] = 1;
        for(auto x : ke[u]){
            int v = x.first;
            ll w = x.second;
            if(v == par) continue;
            d[v] = d[u] + w;
            DFS(v, u);
        }
        vs[u] = 0;
    }

    void solve(){
        dp[1] = 0;
        d[1] = 0;
        DFS(1, -1);
        FOR(i, 2, n) cout << dp[i] << " ";
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    FOR(i, 1, n-1){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        ke[u].PB({v, w});
        ke[v].PB({u, w});
    }
    FOR(i, 2, n) cin >> s[i] >> v[i];
    process::solve();
    return 0;
}

• Subtask 1: 20 / 100