CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:T
Submission time:2021-10-16 04:03:25
Language:C++11
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.19 s1, 2, 3details
#2--2, 3details
#30.01 s3details

Code

/**
 * Datathti 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 details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)