chromosome

/// Silion Liviu
/// Se bazeaza pe ideea asta rezolvarea: https://prnt.sc/tzpbeg.
/// Se face un vector pentru fiecare traseu pentru a verifica sa nu fie niciun loop si pentru a putea reconstitui traseul.

#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <functional>
#include <algorithm>
#include <iostream>

using Ip = std::pair<int, int>;
using Vp = std::pair<int, std::vector<int>>;
using Vi = std::vector<int>;
using Vb = std::vector<bool>;

namespace std
{
    class InParser
    {
    public:
        InParser(const char *file_name)
        {
            input_file.open(file_name, std::ios::in);
            input_file.sync_with_stdio(false);
            index = 0;
            input_file.read(buffer, SIZE);
        }
        InParser &operator>>(int &n)
        {
            for (; !std::isdigit(buffer[index]); increment())
                ;
            n = 0;
            for (; std::isdigit(buffer[index]); increment())
                n = n * 10 + (buffer[index] - '0');
            return *this;
        }
        ~InParser()
        {
            input_file.close();
        }

    private:
        std::fstream input_file;
        static const int SIZE = 0x1000;
        int index;
        char buffer[SIZE];
        void increment()
        {
            if (++index == SIZE)
                index = 0, input_file.read(buffer, SIZE);
        }
    };
    class OutParser
    {
    public:
        OutParser(const char *file_name)
        {
            output_file.open(file_name, std::ios::out);
            output_file.sync_with_stdio(false);
            index = 0;
        }
        OutParser &operator<<(int64_t target)
        {
            if (target < 10)
                increment(target + '0');
            else
            {
                (*this) << (target / 10);
                increment(target % 10 + '0');
            }
            return *this;
        }
        OutParser &operator<<(int target)
        {
            if (target < 10)
                increment(target + '0');
            else
            {
                (*this) << (target / 10);
                increment(target % 10 + '0');
            }
            return *this;
        }
        OutParser &operator<<(const char *target)
        {
            int aux = 0;
            while (target[aux])
                increment(target[aux++]);
            return *this;
        }
        ~OutParser()
        {
            output_file.write(buffer, index);
            output_file.close();
        }

    private:
        std::fstream output_file;
        static const int SIZE = 0x1000;
        int index;
        char buffer[SIZE];
        void increment(char ch)
        {
            if (index == SIZE)
                index = 0, output_file.write(buffer, SIZE), buffer[index++] = ch;
            else
                buffer[index++] = ch;
        }
    };
    OutParser &operator<<(OutParser &flux, const Vp &p)
    {
        flux << /*"weight " <<*/ p.first << " " << (int)p.second.size() << "\n" /*" using path: "*/;
        for (const auto &it : p.second)
            flux << it << " ";
        flux << "\n";
        return flux;
    }
    ofstream &operator<<(ofstream &flux, const Vp &p)
    {
        flux << /*"weight " <<*/ p.first << " " << p.second.size() << "\n" /*" using path: "*/;
        for (const auto &it : p.second)
            flux << it << " ";
        flux << "\n";
        return flux;
    }
    ostream &operator<<(ostream &flux, const Vi &p)
    {
        for (const auto &it : p)
            flux << it << " ";
        return flux;
    }
    ostream &operator<<(ostream &flux, const Vp &p)
    {
        flux << "weight " << p.first << " using path: ";
        for (const auto &it : p.second)
            flux << it << " ";
        flux << "\n";
        return flux;
    }
    template <>
    struct greater<Vp> : binary_function<Vp, Vp, bool>
    {
        bool operator()(const Vp &p1, const Vp &p2) const
        {
            if (p1.first != p2.first)
                return p1.first > p2.first;
            vector<int> v1 = p1.second, v2 = p2.second;
            reverse(v1.begin(), v1.end()), reverse(v2.begin(), v2.end());
            return v1 > v2;
        }
    };
}; // namespace std

std::InParser fin("chromosome.in");
std::OutParser fout("chromosome.out");

int V, E, K, u, v, w, src, dest;
std::vector<std::vector<Ip>> Graph;
std::vector<Vp> Path;
Vi Count, Curr, New;
Vb Seen;
std::priority_queue<Vp, std::vector<Vp>, std::greater<Vp>> PQ;

int main()
{
    fin >> V >> E >> K >> src >> dest;
    Graph.resize(V + 1), Count.assign(V + 1, 0);
    for (int i = 1; i <= E; ++i)
        fin >> u >> v >> w,
            Graph[u].emplace_back(std::make_pair(v, w));
    //Graph[v].emplace_back (std::make_pair (u, w));

    Curr.push_back(src);
    PQ.push(std::make_pair(0, Curr));
    while (!PQ.empty() && Count[dest] < K)
    {
        Curr = PQ.top().second;
        //std::cout << PQ.top ();
        int cost = PQ.top().first, u = Curr.back();
        PQ.pop(), ++Count[u];
        if (u == dest)
            Path.emplace_back(std::make_pair(cost, Curr));
        if (Count[u] <= K)
        {
            for (const auto &it : Graph[u])
            {
                New = Curr;
                Seen.assign(V + 1, false);
                for (const auto &it : New)
                    Seen[it] = true;
                if (!Seen[it.first])
                    New.emplace_back(it.first),
                        PQ.push(std::make_pair(cost + it.second, New));
            }
        }
    }

    fout << (int)Path.size() << "\n";
    for (const auto &it : Path)
        fout << it;

    //fin.close (), fout.close ();
    return 0;
}