Submission #641161

#TimeUsernameProblemLanguageResultExecution timeMemory
641161sumit_kk10Harbingers (CEOI09_harbingers)C++17
20 / 100
1098 ms36560 KiB
#include<bits/stdc++.h> #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) #define pb push_back #define F first #define S second #define int long long using namespace std; const int N = 1e6 + 5, MOD = 1e9 + 7; vector<pair<int, int> > g[N]; int n, par[N], dis[N], dp[N], s[N], d[N]; bool vis[N]; void dfs(int node, int p, int sum){ dis[node] = sum; par[node] = p; for(auto k : g[node]){ if(k.F == p) continue; dfs(k.F, node, sum + k.S); } } void bfs(int node){ queue<int> q; q.push(node); vis[node] = true; while(!q.empty()){ int node = q.front(); q.pop(); if(node != 1){ // calculate dp[node] int cur = par[node]; dp[node] = LLONG_MAX; while(cur != 0){ int x = (dis[node] - dis[cur]) * d[node]; dp[node] = min(dp[node], x + dp[cur] + s[node]); cur = par[cur]; } } for(auto k : g[node]){ if(!vis[k.F]){ vis[k.F] = true; q.push({k.F}); } } } } void solve(){ cin >> n; for(int i = 1; i < n; ++i){ int u, v, c; cin >> u >> v >> c; g[u].pb({v, c}); g[v].pb({u, c}); } for(int i = 1; i < n; ++i) cin >> s[i + 1] >> d[i + 1]; dfs(1, 0, 0); bfs(1); for(int i = 2; i <= n; ++i) cout << dp[i] << " "; } int32_t main(){ fast; int t = 1; // cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...