CSES - Aalto Competitive Programming 2024 - wk6 - Homework - Results
Submission details
Task:Shortest Routes I
Sender:fabiank
Submission time:2024-10-07 15:17:17 +0300
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.13 sdetails
#7ACCEPTED0.14 sdetails
#8ACCEPTED0.13 sdetails
#9ACCEPTED0.13 sdetails
#10ACCEPTED0.13 sdetails
#11ACCEPTED0.08 sdetails
#12ACCEPTED0.07 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.07 sdetails
#15ACCEPTED0.07 sdetails
#16ACCEPTED0.06 sdetails
#17ACCEPTED0.07 sdetails
#18ACCEPTED0.09 sdetails

Code

#include <bits/stdc++.h>

#define REP(i, a, b) for (int i = a; i < b; i++)

// Type Aliases for 1D and 2D vectors with initialization
#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val
#define ll long long
#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val))              // 2D vector of ints (n x m), initialized to val
#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val

using namespace std;

void print_vector(vector<int> &x)
{
    for (int v : x)
    {
        cout << v << " ";
    }
    cout << "\n";
}

void print_matrix(vector<vector<int>> &matrix)
{
    cout << "\n"
         << "----------------" << "\n";
    for (vector<int> row : matrix)
    {
        print_vector(row);
    }
    cout << "\n"
         << "----------------" << "\n";
}

int calc_max_digit(int n)
{
    int max_digit = 0;
    while (n > 0 && max_digit < 9)
    {
        int digit = n % 10;
        if (digit > max_digit)
        {
            max_digit = digit;
        }
        n /= 10;
    }
    return max_digit;
}

// edges as edge list for outgoing node as pairs (end, cost)
vector<ll> dijkstras(int start_point, vector<vector<pair<int, int>>> edges)
{
    int n = edges.size();
    vector<bool> processed(n, false);
    vector<ll> distances(n, LLONG_MAX);
    distances[start_point] = 0;
    priority_queue<pair<ll, int>> pq;
    pq.push({0, start_point});
    while (!pq.empty())
    {
        int curr = pq.top().second;
        pq.pop();
        if (processed[curr])
        {
            continue;
        }
        processed[curr] = true;
        ll distance = distances[curr];

        for (pair<int, int> edge : edges[curr])
        {

            if (distance + edge.second < distances[edge.first])
            {
                distances[edge.first] = distance + edge.second;
                pq.push({-distances[edge.first], edge.first});
            }
        }
    }
    return distances;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> edges(n, vector<pair<int, int>>(0));

    for (int i = 0; i < m; i++)
    {
        int start, end, cost;
        cin >> start >> end >> cost;
        edges[start - 1].push_back({end - 1, cost});
    }

    vector<ll> result = dijkstras(0, edges);

    for (ll dist : result)
    {
        cout << dist << " ";
    }
    cout << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
10 20
8 5 1
9 10 2
7 9 8
9 8 8
...

correct output
0 9 11 20 13 14 19 29 27 29 

user output
0 9 11 20 13 14 19 29 27 29 

Test 2

Verdict: ACCEPTED

input
10 20
5 6 4
5 1 7
7 4 4
7 8 1
...

correct output
0 7 9 17 15 17 21 22 25 30 

user output
0 7 9 17 15 17 21 22 25 30 

Test 3

Verdict: ACCEPTED

input
10 20
1 4 1
4 2 1
9 10 1
1 2 4
...

correct output
0 2 11 1 2 7 16 18 12 13 

user output
0 2 11 1 2 7 16 18 12 13 

Test 4

Verdict: ACCEPTED

input
10 20
6 3 5
7 5 8
5 1 8
8 9 5
...

correct output
0 5 9 18 22 10 14 23 27 36 

user output
0 5 9 18 22 10 14 23 27 36 

Test 5

Verdict: ACCEPTED

input
10 20
8 9 3
2 3 8
10 5 3
2 5 3
...

correct output
0 8 16 18 11 17 24 23 16 26 

user output
0 8 16 18 11 17 24 23 16 26 

Test 6

Verdict: ACCEPTED

input
100000 200000
18000 18001 426710313
73018 73012 558438094
87726 87671 355171790
53170 53171 869493690
...

correct output
0 479659405 1165315262 1854343...

user output
0 479659405 1165315262 1854343...
Truncated

Test 7

Verdict: ACCEPTED

input
100000 200000
26504 26450 258578924
49543 49544 28958186
75174 75175 89459846
39175 39228 119699475
...

correct output
0 655556128 1413395076 1814086...

user output
0 655556128 1413395076 1814086...
Truncated

Test 8

Verdict: ACCEPTED

input
100000 200000
39477 39413 773046299
69758 69759 558754983
23279 23280 142570619
61416 61479 874921013
...

correct output
0 269736525 626115013 70199222...

user output
0 269736525 626115013 70199222...
Truncated

Test 9

Verdict: ACCEPTED

input
100000 200000
76662 76636 844365635
73339 73342 755006676
89878 89879 396562588
18801 18781 954807004
...

correct output
0 598585836 1267139909 1803859...

user output
0 598585836 1267139909 1803859...
Truncated

Test 10

Verdict: ACCEPTED

input
100000 200000
11724 11725 818399968
33244 33197 722525474
65530 65531 483965413
62405 62454 199581867
...

correct output
0 387990617 441010945 92441292...

user output
0 387990617 441010945 92441292...
Truncated

Test 11

Verdict: ACCEPTED

input
100000 200000
1 2 1
1 3 1
1 4 1
1 5 1
...

correct output
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

user output
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
Truncated

Test 12

Verdict: ACCEPTED

input
100000 99999
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
...

correct output
0 1000000000 2000000000 300000...

user output
0 1000000000 2000000000 300000...
Truncated

Test 13

Verdict: ACCEPTED

input
1 1
1 1 1

correct output

user output

Test 14

Verdict: ACCEPTED

input
99999 149997
1 2 1
2 3 1
3 4 1
4 5 1
...

correct output
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 ...

user output
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 ...
Truncated

Test 15

Verdict: ACCEPTED

input
99997 149994
1 3 3
3 5 3
5 7 3
7 9 3
...

correct output
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

user output
0 1 2 3 4 5 6 7 8 9 10 11 12 1...
Truncated

Test 16

Verdict: ACCEPTED

input
60003 120000
1 2 30010
1 3 30010
1 4 30010
1 5 30010
...

correct output
0 30010 30010 30010 30010 3001...

user output
0 30010 30010 30010 30010 3001...
Truncated

Test 17

Verdict: ACCEPTED

input
60003 120000
1 2 30010
1 3 30010
1 4 30010
1 5 30010
...

correct output
0 30010 30010 30010 30010 3001...

user output
0 30010 30010 30010 30010 3001...
Truncated

Test 18

Verdict: ACCEPTED

input
100000 149997
1 50000 99997
1 49999 99995
1 49998 99993
1 49997 99991
...

correct output
0 1 3 5 7 9 11 13 15 17 19 21 ...

user output
0 1 3 5 7 9 11 13 15 17 19 21 ...
Truncated