/*
Konstruisati algoritam linearne slozenosti koji za dati tezinski graf
nalazi putanju maksimalne cene od datog polaznog cvora do datog dolaznog cvora
tako da je cena veca od datog celog broja x. 
Putanja ne sme da sadrzi ciklus.
*/
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <climits>
using namespace std;
 
// smestamo grane grafa
struct Edge {
    int src, dest, weight;
};
 
// predstava grafa
class Graph
{
    public:
    // vektor vektora strukture  Edge koristimo da predstavimo listu susedstva
    vector<vector<Edge>> adjList;
 
    // Konstruktora
    Graph(vector<Edge> const &edges, int N)
    {
        // resize za vektor da prihvati N elemenata tipa vector<Edge>
        adjList.resize(N);
 
        // dodati grane u usmereni graf
        for (auto &edge: edges)
        {
            int src = edge.src;
            int dest = edge.dest;
            int weight = edge.weight;
 
            adjList[src].push_back({src, dest, weight});
            adjList[dest].push_back({dest, src, weight});
        }
    }
};
 
// BFS cvor
struct Node
{
    // tekuci broj cvora i cena tekuce putanje
    int vertex, weight;
 
    // skup trenutno posecenih cvorova u tekucoj putanji
    set<int> s;
};
 
// Izvedeti BFS na grafu g pocevsi pretragu u cvoru v
int modifiedBFS(Graph const &g, int src, int k)
{
    // kreirati red za BFS
    queue<Node> q;
 
    // dodati u skup polazni cvor i smestiti u red
    set<int> vertices;
    vertices.insert(0);
    q.push({src, 0, vertices});
 
    // pamtimo maksimalnu cenu putanje od polaznog cvora
    int maxCost = INT_MIN;
 
    // dokle god nije red prazan 
    while (!q.empty())
    {
        // skini cvor iz queue
        Node node = q.front();
        q.pop();
 
        int v = node.vertex;
        int cost = node.weight;
        vertices = node.s;
 
        // ako dolazni cvor je dostizan i BFS dubina je jednaka m
        // azurirajmo minimalnu cenu izracunatu do sada
        if (cost > k)
            maxCost = max(maxCost, cost);
 
        // za svaku granu incidentnu cvoru v
        for (Edge edge : g.adjList[v])
        {
            // proveri ciklus
            if (vertices.find(edge.dest) == vertices.end())
            {
                // dodaj tekuci cvor u putanju
                set<int> s = vertices;
                s.insert(edge.dest);
 
                // postaviti svaki cvor  (obradjen ili ne) u red
                // sa cenom jednakom  (cena roditelja  + tezina
                // tekuce grane)
                q.push( {edge.dest, cost + edge.weight, s} );
            }
        }
    }
 
    // vratiti max cenu
    return maxCost;
}
 

int main()
{
    // graf
    vector<Edge> edges =
    {
        {0, 6, 11}, {0, 1, 5}, {1, 6, 3}, {1, 5, 5}, {1, 2, 7},
        {2, 3, -8}, {3, 4, 10}, {5, 2, -1}, {5, 3, 9}, {5, 4, 1},
        {6, 5, 2}, {7, 6, 9}, {7, 1, 6}
    };
 
    // broj cvorova grafa
    int N = 9;
 
    // kreiraj graf 
    Graph g(edges, N);
 
    int src = 0;
    int cost = 50;
 
    // modifikovana BFS pretraga od izvora do odrediste 
    int maxCost = modifiedBFS(g, src, cost);
 
    if (maxCost != INT_MIN)
        cout << maxCost;
    else
        cout << "Sve putanje od izvornog cvora do dolaznog cvora imaju istu manju cenu  " << cost;
 
    return 0;
}