test 7 - 2018-2019

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <climits>
using namespace std;

unordered_map<int, vector<pair<int, int>>> graph;
unordered_map<int, int> mostCommon;


void dfs(int currWeight, int currIdx, int k, int currK, vector<bool>& visited){
    if(currK == k){
        mostCommon[currWeight]++;
        return;
    }
    visited[currIdx] = true;

    for (auto neighbour : graph[currIdx]) {
            int nextWeight = currWeight + neighbour.second;
            int nextIdx = neighbour.first;
            int nextK = currK + 1;

            if (!visited[nextIdx])
                dfs(nextWeight, nextIdx, k, currK + 1, visited);
    }
    visited[currIdx] = false;
}

void mostCommonFor(int v, int k, int numOfV) {
    vector<bool> visited(numOfV, false);

    dfs(0, v, k, 0, visited);
}

int main() {
    int v, e, x, y, w, k;
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        cin >> x >> y >> w;
        graph[x - 1].push_back({ y - 1, w });
    }
    cin >> k;

    for (int i = 0; i < v; i++) {
        mostCommonFor(i, k, v);
    }

    int result = -1;
    int resultVal = -1;
    mostCommon[-1] = 0;

    for (auto res : mostCommon) {
        if (result < res.second || (result == res.second && res.first > resultVal)) {
            result = res.second;
            resultVal = res.first;
        }
    }
    cout << resultVal;
    return 0;
}