m_graph

#include "bits/stdc++.h"

using namespace std;

class Graph{
public:


    Graph(long long size) : visited(size, false) {
        for(long long i = 0; i < size; ++i) {
            matrix.push_back(vector<long long>(size,0));
            string s;
            cout << "Enter name " << i + 1 << " vertex: ";
            cin >> s;
            nodes.push_back(s);
            node_to_index[s] = i;
        }
    }

    long long first(string v) {
        long long index = node_to_index[v];
        for(long long i = 0; i < matrix[index].size(); ++i) {
            if (matrix[index][i] != 0)
                return i;
        }
        return -1;
    }

    long long next(string v, long long in) {
        long long index = node_to_index[v];
        for (long long i = in + 1; i < matrix[index].size(); ++i) {
            if (matrix[index][i] != 0)
                return i;
        }
        return -1;
    }

    string vertex(string v, int i) {
        if (matrix[node_to_index[v]][i])
            return nodes[i];
        return "";
    }

    void add_v(string v) {
        node_to_index[v] = matrix.size();
        nodes.push_back(v);
        matrix.push_back(vector<long long>(matrix[0].size(), 0));
        for(auto& x : matrix) {
            if(!x.empty())
                x.push_back(0);
        }
    }

    void add_e(string v, string w, int c) {
        matrix[node_to_index[v]][node_to_index[w]] = c;
    }

    void del_v(string v) {
        long long index = node_to_index[v];
        matrix.erase(matrix.begin() + index);
        visited.erase(visited.begin() + index);
        nodes.erase(nodes.begin() + index);
        node_to_index.erase(v);
        for(long long i = 0; i < matrix.size(); ++i)
            matrix.erase(matrix.begin() + index);
        for (auto& x : node_to_index)
            if (x.second > index)
                --x.second;
    }

    void del_e(string v, string w) {
        matrix[node_to_index[v]][node_to_index[w]] = 0;
    }

    void edit_v(string v, bool mark) {
        visited[node_to_index[v]] = mark;
    }

    void edit_e(string v, string w, int c) {
        matrix[node_to_index[v]][node_to_index[w]] = c;
    }

    void print() {
        for(long long i = 0; i < matrix.size(); ++i) {
            for (long long j = 0; j < matrix[i].size(); ++j) {
                cout << matrix[i][j] << ' ';
            }
            cout << endl;
        }
    }

    long long get_weight(string first, string second) {
        long long i = node_to_index[first], j = node_to_index[second];
        if (i < matrix.size() && j < matrix.size())
            return matrix[i][j];
        else throw runtime_error("l");
    }

    bool is_visited(string node) {
        return visited[node_to_index[node]];
    }

    vector<string> get_nodes() {
        return nodes;
    }

private:

    vector<string> nodes;
    vector<bool> visited;
    vector<vector<long long>> matrix;
    unordered_map<string, long long> node_to_index;

};


void dfs(Graph g, string name, vector<vector<string> >& res, long long int k, vector<string> way) {
    if (g.is_visited(name) || k < 0)
        return;
    way.push_back(name);
    if (k == 0) {
        res.push_back(way);
        return;
    }
    g.edit_v(name, true);
    for (long long index = g.first(name); index != -1; index = g.next(name, index)) {
        auto v = g.vertex(name, index);
        dfs(g, v, res, k - g.get_weight(name, v), way);
    }
    g.edit_v(name, false);
}

vector<vector<string> > get_ways(Graph g, long long int k) {
    vector<vector<string> > res;
    for (auto& x : g.get_nodes()) {
        vector<string> way = {};
        dfs(g, x, res, k, way);
    }
    return res;
}

int main(){
    int size;
    cout << "Enter graph size: ";
    cin >> size;
    Graph G(size);
    int cCount, n;
    cout << "Enter edge count: ";
    cin >> cCount;
    cout << "Enter k:";
    cin >> n;
    for(int i = 0; i < cCount; ++i){
        string first_v, second_v;
        int weight;
        cout << "Enter " << (i + 1) << " edge: ";
        cin >> first_v >> second_v >> weight;
        G.add_e(first_v, second_v, weight);
    }
    G.print();
    cout << endl;
    vector<vector<string>> ways = get_ways(G, n);
    cout << "Found " << ways.size() << " ways:\n";
    for (auto& x : ways) {
        for (auto &y: x)
            cout << y << ' ';
        cout << endl;
    }
    return 0;
}