// Example program
#include <iostream>
#include <string>

using namespace std;

void array() {
    const int inf = 100;
    // liczba rzedow = ilosc krawedzi
    // start - end - value
    int arcs[8][3] = {
            {6, 4, 5},
            {6, 5, 4},
            {5, 3, -2},
            {5, 2, 1},
            {4, 3, 3},
            {2, 1, 1},
            {3, 2, -3},
            {3, 1, 3}
    };
// wielkosc tablicy = ilosc wierzcholkow
    int nodes[6] = {inf, inf, inf, inf, inf, 0};
    int pi[6] = {-1, -1, -1, -1, -1, -1};
    for (int i = 0; i < 5; i++) {
        for (auto & arc : arcs) {
            int start = arc[0] - 1;
            int end = arc[1] - 1;
            int value = arc[2];
            if (nodes[end] > value + nodes[start]) {
                nodes[end] = value + nodes[start];
                pi[end] = start + 1;
            }
        }
    }

    cout << "array algorithm" << "\n";

    for (int node : nodes) {
        cout << node << " ";
    }

    cout << "\npi\n";
    for (int i : pi) {
        cout << i << " ";
    }

    for (auto & arc : arcs) {
        int start = arc[0] - 1;
        int end = arc[1] - 1;
        int value = arc[2];
        if (nodes[end] > value + nodes[start]) {
            cout << "error";
        }
    }
}

void list() {
    const int inf = 100;
    // start - end - value
    int arcs[24] = {6, 4, 5, 6, 5, 4, 5, 3, -2, 5, 2, 1, 4, 3, 3, 2, 1, 1, 3, 2, -3, 3, 1, 3};
    // wielkosc tablicy = ilosc wierzcholkow
    int nodes[6] = {inf, inf, inf, inf, inf, 0};
    int pi[6] = {-1, -1, -1, -1, -1, -1};
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 24; j += 3) {
            int start = arcs[j] - 1;
            int end = arcs[j + 1] - 1;
            int value = arcs[j + 2];
            if (nodes[end] > value + nodes[start]) {
                nodes[end] = value + nodes[start];
                pi[end] = start + 1;
            }
        }
    }

    cout << "list algorithm" << "\n";

    for (int node : nodes) {
        cout << node << " ";
    }

    cout << "\npi\n";
    for (int i : pi) {
        cout << i << " ";
    }

    for (int j = 0; j < 23; j += 3) {
        int start = arcs[j] - 1;
        int end = arcs[j + 1] - 1;
        int value = arcs[j + 2];
        if (nodes[end] > value + nodes[start]) {
            cout << "error";
        }
    }
}

int main()
{
    array();
    cout << "\n";
    list();
}