Tietoverkko

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

pair<bool, int> getShortest(vector<vector<pair<int, int>>> computers, int comp1, int comp2, int prev)
{
    for (unsigned int i = 0; i < computers[comp1].size(); i++)
    {
        if (computers[comp1][i].first == prev)
        {
            continue;
        }
        if (computers[comp1][i].first == comp2)
        {
            // next to
            return make_pair(true, computers[comp1][i].second);
        }
        pair<int, int> data = getShortest(computers, computers[comp1][i].first, comp2, comp1);
        if (data.first)
        {
            return make_pair(true, min(data.second, computers[comp1][i].second));
        }
    }
    return make_pair(false, 0);
}

int main(int argc, char **argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll total = 0;

    int amount;
    cin >> amount;

    vector<vector<pair<int, int>>> computers(amount);

    for (int i = 0; i < amount - 1; i++)
    {
        int a, b, x;
        cin >> a >> b >> x;
        computers[a - 1].push_back(pair<int, int>(b - 1, x));
        computers[b - 1].push_back(pair<int, int>(a - 1, x));
    }

    map<int, bool> went;

    for (int i = 0; i < amount; i++)
    {
        for (int j = 0; j < amount; j++)
        {
            if (i != j && !(went[i | (j << 9)] || went[j | (i << 9)]))
            {
                went[i | (j << 9)] = true;
                went[j | (i << 9)] = true;
                total += getShortest(computers, i, j, -1).second;
            }
        }
    }

    cout << total << "\n";
}

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED