Tietoverkko

/**
 * Datatähti 2022 alku
 * Tietoverkko (Network)
 * @author TRS
 */
#include <bits/stdc++.h>
using namespace std;
//Constants
#define infinity 0x3f3f3f3f
#define linfinity 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
const int MX = 200001;
long long routeSpeed[MX], sourceNode[MX], nodeStatus[MX];
long long Answer;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    long long network[n][n] = {0};
    int a, b;
    long long x;
    for (int connection = 0; connection < n - 1; connection++) {
        cin>>a>>b>>x;
        network[a - 1][b - 1] = x;
        network[b - 1][a - 1] = x;
    }
    int u, v;
    for (int source = 0; source < n - 1; source++) {
        for (int destination = source + 1; destination < n; destination++) {
            for (int i = 0; i < n; i++) {
                routeSpeed[i] = linfinity;
                sourceNode[i] = -1;
                nodeStatus[i] = 0;
            }
            routeSpeed[source] = 0;
            for (int i = 0; i < n - 1; i++) {
                long long minimum = linfinity;
                u = 0;
                for (v = 0; v < n; v++) {
                    if (nodeStatus[v] == 0 && routeSpeed[v] <= minimum) {
                        minimum = routeSpeed[v];
                        u = v;
                    }
                }
                if (u == destination) {
                    break;
                }
                nodeStatus[u] = 1;
                for (v = 0; v < n; v++) {
                    if (nodeStatus[v] == 0 && network[u][v] != 0 && routeSpeed[u] + network[u][v] < routeSpeed[v]) {
                        sourceNode[v] = u;
                        routeSpeed[v] = routeSpeed[u] + network[u][v];
                    }
                }
            }
            long long answer = linfinity;
            long long to = destination, from = sourceNode[to];
            while (from != -1) {
                answer = min(answer, network[from][to]);
                to = from;
                from = sourceNode[to];
            }
            Answer += answer;
        }
    }
    cout<<Answer<<"\n";
    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: RUNTIME ERROR