#include <climits>
#include <iostream>
#include <list>
#include <ostream>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

// NOTE:
// -> this approach can be used on both directed and undirected graphs
// Limitations of Dijkstra's Algorithm:
//  - Inapplicable to graphs with negative edge weights.
//  - Unable to handle graphs containing negative cycles.
//  - Does not provide information about unreachable nodes.

// Class representing a directed weighted graph
class DirectedWeightedGraph {
public:
  // Adjacency List representation: <vertex value, <neighbor, weight>>
  unordered_map<int, list<pair<int, int>>> adjacencyList;

  // Function to insert an edge into the graph
  void insertEdge(int source, int destination, int weight, bool isDirected) {
    if (isDirected) {
      // For directed graph, only one entry is added for the source to
      // destination
      adjacencyList[source].push_back({destination, weight});
    } else {
      // For undirected graph, entries are added for both source to destination
      // and destination to source
      adjacencyList[source].push_back({destination, weight});
      adjacencyList[destination].push_back({source, weight});
    }
  }

  // Function to print the adjacency list
  void printAdjacencyList() {
    for (auto vertex : adjacencyList) {
      cout << vertex.first << " : ";
      for (auto neighbor : vertex.second) {
        cout << " { " << neighbor.first << " , " << neighbor.second << " } ";
      }
      cout << endl;
    }
  }

  // NOTE: unlike directed graphs here we can't use topological sort to get the
  // element in a dependency order
  // -> so we use min min-heap or set to get the node with the min distance .
  // -> isentially it's bfs only but here we are using set instead of queue .

  // Function to find the shortest paths using Dijkstra's algorithm
  vector<int> dijkstrasShortestPath(int source, int numberOfNodes) {

    // Vector to store the shortest distances from the source to each node
    // NOTE: using unordered_map could be a better / vercitle chaoice
    // -> as we won't need to handle the indexes manually then
    vector<int> shortestDistances(numberOfNodes + 1, INT_MAX);

    // Set to keep track of nodes and their distances, sorted by distance
    // NOTE: using min-heap could be a better chaoice here
    //  -> but then we'll have to write a custom comparator for it .
    set<pair<int, int>> nodesSet;

    // insert a source node into set and mark it's distance as 0
    nodesSet.insert({0, source});
    shortestDistances[source] = 0;

    // Dijkstra's algorithm
    while (!nodesSet.empty()) {

      // Get the node with the smallest distance
      auto currentNode = nodesSet.begin();

      // as a .begin() returns an itirator we need to dereference it with *
      auto currentPair = *(currentNode);

      // get the current node value and it's shortest distance so far
      int currentNodeValue = currentPair.second;
      int currentNodeDistance = currentPair.first;

      // Remove the current node from the set
      nodesSet.erase(nodesSet.begin());

      // Iterate over neighbors of the current node
      for (auto neighborPair : adjacencyList[currentNodeValue]) {

        // take the neighborDistance and neighborNodeValue out of neighborPair
        int neighborNodeValue = neighborPair.first;
        int neighborDistance = neighborPair.second;

        // Update the distance if the currentNodeDistance in addition to the
        // distance to the neighbor from the current node is smaller to the
        // distance of the neighbor.
        if (currentNodeDistance + neighborDistance <
            shortestDistances[neighborNodeValue]) {

          // Remove the previous entry for the neighbor from the set
          auto previousEntry = nodesSet.find(
              {shortestDistances[neighborNodeValue], neighborNodeValue});

          // if the previous entry of a neighbor pair is found erase it
          if (previousEntry != nodesSet.end()) {
            nodesSet.erase(previousEntry);
          }

          // Update the shortest distance for the neighbor node
          shortestDistances[neighborNodeValue] =
              currentNodeDistance + neighborDistance;

          // insert the updated entry back into the set for further processing
          // NOTE: we are inserting this updated neighbor into the set to
          // process it's neighbors and recalculate their distances accordingly.
          nodesSet.insert(
              {shortestDistances[neighborNodeValue], neighborNodeValue});
        }
      }
    }
    return shortestDistances;
  }
};

int main() {

  // Create a directed weighted graph object
  DirectedWeightedGraph weightedGraph;

  // Add edges to the graph
  weightedGraph.insertEdge(1, 6, 14, false);
  weightedGraph.insertEdge(1, 3, 9, false);
  weightedGraph.insertEdge(1, 2, 7, false);
  weightedGraph.insertEdge(2, 3, 10, false);
  weightedGraph.insertEdge(2, 4, 15, false);
  weightedGraph.insertEdge(3, 4, 11, false);
  weightedGraph.insertEdge(6, 3, 2, false);
  weightedGraph.insertEdge(6, 5, 9, false);
  weightedGraph.insertEdge(5, 4, 6, false);

  // Specify the source node and the total number of nodes in the graph
  int sourceNode = 6;
  int totalNodes = 6;

  // Find the shortest paths from the source to all nodes
  vector<int> shortestPaths =
      weightedGraph.dijkstrasShortestPath(sourceNode, totalNodes);

  // Print the adjacency list of the graph
  // weightedGraph.printAdjacencyList();

  // Display the shortest paths from the source to each node
  cout << "Shortest path from " << sourceNode << " to each node is : " << endl;

  // Print the shortest path lengths
  for (int i = 0; i < shortestPaths.size(); i++) {
    cout << i << " -> " << shortestPaths[i] << endl;
  }
  cout << endl;
}