bellman-ford

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <utility>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

struct vertex
{
    int level, number;
    vertex() : level{-1}, number{-1} {}
    vertex(int l, int n) : level{l}, number{n} {}
    bool operator<(const vertex& other) const
    {
        if (level < other.level)
            return true;
        if (level > other.level)
            return false;
        return number < other.number;
    }
    bool operator==(const vertex& other) const
    {
        return level == other.level && number == other.number;
    }
};

//following hash code is found from stackoverflow link below.
namespace std {
    
    template <>
    struct hash<vertex>
    {
        std::size_t operator()(const vertex& k) const
        {
            using std::size_t;
            using std::hash;
            
            // Compute individual hash values for first,
            // second and third and combine them using XOR
            // and bit shifting:
            
            return ((hash<int>()(k.level)
                     ^ (hash<int>()(k.number) << 1)) >> 1);
        }
    };
    
}

//Key hasher retrieved from http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-typ//-as-the-key


class nthLevelGraph
{
public:
    void BellmanFord()
    {
        for (auto& v : vertices)
        {
            
            if (v.level == 0)
                smallestWeights[v] = 0;
            else
                smallestWeights[v] = numeric_limits<int>::max() /2;
            //predessors[v] = vertex{};
        }
        for (int i = 1; i < vertices.size(); ++i)
        {
            bool didMakeChanges = false;
            for (auto& edge : edges)
            {
                auto fromSmallest = smallestWeights.find(edge.from);
                auto toSmallest = smallestWeights.find(edge.to);
                
                if(fromSmallest->second + edge.weight < toSmallest->second)
                {
                    didMakeChanges = true;
                    smallestWeights[toSmallest->first] = fromSmallest-> second + edge.weight;
                    predessors[toSmallest->first] = fromSmallest->first;
                }
            }
            if (!didMakeChanges) break;
        }
    }
    
    int shortestPathToNth()
    {
        int minPath = numeric_limits<int>::max();
        
        for (auto it = smallestWeights.begin(); it != smallestWeights.end(); ++it)
        {
            if ((it->first).level == nthLevel)
            {
                if (it->second < minPath)
                {
                    minPath = it->second;
                }
            }
        }
        
        return minPath;
    }
    
    void takeInput()
    {
        cin >> nthLevel;
        
        vertices.insert(vertex{0, 1});
        
        for (int i = 1; i <= nthLevel; ++i)
        {
            int k;
            cin >> k;
            for (int j = 1; j <= k; ++j)
            {
                do
                {
                    int f, w;
                    
                    cin >> f;
                    if (f == 0) 
                        break;
                    cin >> w;
                    
                    auto to = vertices.insert(vertex{i, j});
                    auto from = vertices.insert(vertex{i - 1, f});
                    
                    edges.push_back(edge{*(from.first), (*(to.first)), w});
                    
                }
                while(true);
            }
            if (i != nthLevel)
            {
                string ast;
                cin >> ast;
            }
           
        }
        
    }
private:
    struct edge
    {
        vertex from, to;
        int weight;
        edge(vertex from, vertex to, int weight):
        from{from}, to{to}, weight{weight} {}
    };
    
    unordered_set<vertex> vertices;
    vector<edge> edges;
    unordered_map<vertex, int> smallestWeights;
    unordered_map<vertex, vertex> predessors;
    
    int nthLevel;
};

int main()
{
    nthLevelGraph graph{};
    graph.takeInput();
    graph.BellmanFord();
    cout << graph.shortestPathToNth();
    return 0;
}