제출 #1067184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067184		parlimoos	Harbingers (CEOI09_harbingers)	C++14	20 / 100	1098 ms	16468 KiB

harbingers

#include<iostream>
#include<algorithm>
#include<array>
#include<vector>
using namespace std;

int n;
long long ps[100000] , inf[100000][2] , dp[100000];
vector<array<int , 2>> tr[100000];
vector<int> pth;

void dfs1(int v = 0 , int p = -1){
    if(p != -1) ps[v] += ps[p];
    for(auto e : tr[v]){
        if(e[0] == p) continue;
        ps[e[0]] += e[1] , dfs1(e[0] , v);
    }
}
void dfs2(int v = 0 , int p = -1){
    if(v == 0){
        dp[v] = 0;
    }else{
        dp[v] = (ps[v] * inf[v][1]) + inf[v][0];
        for(int j : pth){
            dp[v] = min(dp[v] , (ps[v] - ps[j]) * inf[v][1] + inf[v][0] + dp[j]);
        }
    }
    pth.push_back(v);
    for(auto e : tr[v]){
        if(e[0] == p) continue;
        dfs2(e[0] , v);
    }
    pth.pop_back();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1 ; i < n ; i++){
        int v , u , d;
        cin >> v >> u >> d;
        tr[v - 1].push_back({u - 1 , d}) , tr[u - 1].push_back({v - 1 , d});
    }
    for(int i = 1 ; i < n ; i++) cin >> inf[i][0] >> inf[i][1];
    dfs1() , dfs2();
    for(int i = 1 ; i < n ; i++) cout << dp[i] << " ";
}

• Subtask 1: 20 / 100