Find ideal path between improtant noes in cyclic graph https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=keyservers

KeyNodes.cpp

//TASK: https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=keyservers

#include <vector>
#include <cstdio>
#include <stack>
#include <cstdlib>

#ifdef WIN32

int getchar_unlocked() { return getchar(); }

#elif UNIX
/* Do linux stuff */
#endif

using namespace std;

struct edge;

typedef struct node {
    int id;
    vector<edge> connections;
    bool server = false;
    bool server_origin = false;
    bool deleted = false;
    bool start = false;
    int virtual_size = 0;
} node_t;

typedef struct edge {
    node_t *from;
    node_t *to;
    int cost;

    bool deleted() {
        return to->deleted || from->deleted;
    }
} edge_t;

static inline void scanint(int &x) {
    // fastest stdin reading, found on https://stackoverflow.com/questions/27899413/understanding-getchar-unlocked
    register int c = getchar_unlocked();
    x = 0;
    for (; (c < 48 || c > 57); c = getchar_unlocked());
    for (; c > 47 && c < 58; c = getchar_unlocked()) {
        x = (x << 1) + (x << 3) + (c & 15);
    }
}

int main() {
    int edges_count, servers_count;
    scanf("%d %d", &edges_count, &servers_count);

    vector<node_t *> nodes(static_cast<unsigned int>(edges_count));
    vector<node_t *> circle_nodes;

    unsigned int total_cost = 0;
    unsigned int confirmed_cost = 0; // cena jen pro originální servery

    bool created[edges_count] = {false};

    for (int i = 0; i < edges_count; ++i) {
        int from, to, cost;
        scanint(from);
        scanint(to);
        scanint(cost);

        if (!created[from]) {
            nodes[from] = new node_t();
            created[from] = true;
        }

        if (!created[to]) {
            nodes[to] = new node_t();
            created[to] = true;
        }

        edge_t e1, e2;
        e1.to = nodes[to];
        e1.from = nodes[from];

        e2.to = nodes[from];
        e2.from = nodes[to];

        e2.cost = e1.cost = cost;
        nodes[from]->connections.push_back(e1);
        nodes[from]->virtual_size++;

        nodes[from]->id = from;
        nodes[to]->connections.push_back(e2);
        nodes[to]->virtual_size++;

        nodes[to]->id = to;
    }

    int server_ids[servers_count] = {0};
    node_t *start;

    // přidání serverů a startu
    for (int i = 0; i < servers_count; ++i) {
        int id;
        scanint(id);
        nodes[id]->server = true;
        nodes[id]->server_origin = true;
        server_ids[i] = id;

        if (i == 0) {
            nodes[id]->start = true;
            start = nodes[id];
        }
    }

    stack<node_t *> leaves;

    // přidání listů do stacku
    for (int i = 0; i < nodes.size(); ++i) {
        if (!nodes[i]->deleted && nodes[i]->connections.size() == 1) {
            leaves.push(nodes[i]);
        }

        while (!leaves.empty()) {
            node_t *current = leaves.top();
            leaves.pop();

            if (current->server_origin) {
                confirmed_cost = total_cost;
            }

            node_t *next;
            int x;

            // smaž zakázané hrany
            for (x = 0; x < current->connections.size(); ++x) {
                if (!current->connections[x].deleted()) {
                    next = current->connections[x].to;
                    break;
                }
            }

            // pokud jdu ze serveru
            if (current->server) {
                next->server = true;
                total_cost += 2 * current->connections[x].cost; // tam a zpět
            }

            if (current->start) {
                next->start = true;
            }

            current->deleted = true;
            next->virtual_size--;
            if (next->virtual_size == 1)
                leaves.push(next);
        }
    }



    // Zjistit jestli nenĂ­ kruĹľnice reundandnĂ­
    int found = 0;
    for (int i = 0; i < nodes.size(); ++i) {
        if (nodes[i]->deleted) continue;
        if (nodes[i]->server) {
            start = nodes[i];
            found++;
        }
    }

    if (found == 1) {
        // kružnice je nepotřebná
        printf("%d\n", confirmed_cost);
        exit(0);
    }


    int biggestCostBetweenservers = 0;
    int circleCost = 0;
    int temporaryEdgeCost = 0;

    int iterationCounter = 0;
    node_t *current = start;

    while (true) {
        ++iterationCounter;
        if (current == start && iterationCounter > 1) {
            if (temporaryEdgeCost > biggestCostBetweenservers) {
                biggestCostBetweenservers = temporaryEdgeCost;
            }
            goto konec;
        }

        if (current->server && temporaryEdgeCost > biggestCostBetweenservers) {
            biggestCostBetweenservers = temporaryEdgeCost;
            temporaryEdgeCost = 0;
        } else if (current->server)
            temporaryEdgeCost = 0;


        for (int i = 0; i < current->connections.size(); ++i) {
            if (iterationCounter > 2 && current->connections[i].to == start) {
                circleCost += current->connections[i].cost;
                temporaryEdgeCost += current->connections[i].cost;
                current->deleted = true;
                current = current->connections[i].to;
                goto dalsiIerace;
            }

            if (!current->connections[i].deleted()) {
                circleCost = circleCost + current->connections[i].cost;
                temporaryEdgeCost = temporaryEdgeCost + current->connections[i].cost;
                current->deleted = true;
                current = current->connections[i].to;
                goto dalsiIerace;
            }
        }

        dalsiIerace:;
    }

    konec:
    int n = 2 * (circleCost - biggestCostBetweenservers);
    printf("%d\n", (n < circleCost ? 2 * (circleCost - biggestCostBetweenservers) : circleCost) + total_cost);
    return 0;
}