제출 #1223765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223765		BestCrazyNoob	Toll (APIO13_toll)	C++20	0 / 100	1 ms	464 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct Edge {
    int i, j, w;
};

int N, M, K;
vector<vector<pii>> tree;
vector<int> P;
ll res = 0;

bool setup(int curr, int prev, int tar, int w) {
    if (curr == tar) return true;
    for (auto &[c, cw]: tree[curr]) {
        if (c == prev) continue;
        if (setup(c, curr, tar, w)) {
            if (cw == -1) cw = w;
            return true;
        }
    }
    return false;
}

ll eval(int curr, int prev) {
    ll up = P[curr];
    for (auto [c, w]: tree[curr]) {
        if (c == prev) continue;
        const ll upc = eval(c, curr);
        res += w * upc;
        up += upc;
    }
    return up;
}

int main() {
    cin >> N >> M >> K;
    vector<Edge> edges(M);
    for (Edge &e: edges) {
        cin >> e.i >> e.j >> e.w;
        e.i--; e.j--;
    }
    vector<pii> add(K);
    for (pii &e: add) {
        cin >> e.first >> e.second;
        e.first--; e.second--;
    }
    P.resize(N);
    for (int &x: P) cin >> x;
    
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {return a.w < b.w;});

    tree.clear();
    tree.resize(N);
    for (int h = 0; h < K; h++) {
        tree[add[h].first].push_back({add[h].second, -1});
        tree[add[h].second].push_back({add[h].first, -1});
    }

    for (Edge e: edges) {
        if (!setup(e.i, -1, e.j, e.w)) {
            tree[e.i].push_back({e.j, 0});
            tree[e.j].push_back({e.i, 0});
        }
    }

    res = 0;
    eval(0, -1);

    cout << res << '\n';

    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22