Submission #1155241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155241		NeilP	Toll (APIO13_toll)	C++20	0 / 100	0 ms	320 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
using std::pair;
using std::vector;
using std::cout;
using std::cin;
using std::endl;
using std::endl;
using std::swap;

struct Edge{
    long long a;
    long long b;
    long long cost;
};

long long n, m, k;
vector<vector<pair<long long, long long>>> tree;

bool comp(Edge a, Edge b){
    return a.cost < b.cost;
}

vector<long long> parent;
vector<long long> size;
vector<long long> tots;

long long find(long long x){
    if(parent[x] == x)
        return x;
    else
    {
        return (parent[x] = find(parent[x]));
    }
}

void merge(long long x, long long y){
    long long xh = find(x);
    long long yh = find(y);
    if(xh == yh)
        return;
    if(size[xh] > size[yh])
        swap(xh, yh);
    parent[xh] = yh;
    size[yh] += size[xh];
}

pair<long long, long long> dfs(long long x, long long p) // (size, money)
{
    pair<long long, long long> tot = {tots[x], 0};
    for(pair<long long, long long> q: tree[x]){
        if(q.first == p){
            continue;
        }
        pair<long long, long long> res = dfs(q.first, x);
        tot.first += res.first;
        tot.second += 1LL * q.second * res.first;
    }
    return tot;
}

int main()
{
    cin >> n >> m >> k;
    
    for(long long i = 0; i < n; i++){
        parent.push_back(i);
        size.push_back(1);
    }
    
    long long start[20], end[20], toll[20];
    
    vector<Edge> edges;
    for(long long i = 0; i < m; i++){
        long long u, v, c;
        cin >> u >> v >> c;
        u--;
        v--;
        Edge e = {u, v, c};
        edges.push_back(e);
    }
    sort(edges.begin(), edges.end(), comp);
    
    for(long long i = 0; i < k; i++){
        cin >> start[i] >> end[i];
        start[i]--;
        end[i]--;
    }
    
    tots = vector<long long>(n);
    for(long long i = 0; i < n; i++)
        cin >> tots[i];
    
    tree = vector<vector<pair<long long, long long>>>(n);
    
    for(Edge e : edges){
        long long x_comp = find(e.a);
        long long y_comp = find(e.b);
        if(x_comp == y_comp) 
            continue;
        for(long long i = 0; i < k; i++){
            long long u_c = find(start[i]);
            long long v_c = find(end[i]);
            if((u_c == x_comp && v_c == y_comp) || (v_c == x_comp && u_c == y_comp)){
                toll[i] = e.cost;
                tree[start[i]].push_back({end[i], toll[i]});
                tree[end[i]].push_back({start[i], toll[i]});
                merge(x_comp, y_comp);
                break;
            }
        }
        x_comp = find(e.a);
        y_comp = find(e.b);
        if(x_comp == y_comp) 
            continue;
        merge(x_comp, y_comp);
        tree[e.a].push_back({e.b, 0});
        tree[e.b].push_back({e.a, 0});
    }
    
    pair<long long, long long> res = dfs(0, -1);
    cout << res.second << endl;
    

    return 0;
}

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