Seminar8

#include <iostream>
#include <queue>

#include "ListGraph.hpp"
#include "SetGraph.hpp"

void DFSReverseRecursive(size_t u, const IGraph& graph,
                         std::vector<bool>& visited, std::vector<size_t>& to_go) {
  visited[u] = true;
  for (size_t v : graph.FindAllAdjacentIn(u)) {
    if (!visited[v]) DFSReverseRecursive(v, graph, visited, to_go);
  }
  to_go.push_back(u);
}

std::vector<size_t> DFSReverse(const IGraph& graph) {
  std::vector<size_t> to_go;
  std::vector<bool> visited(graph.VerticesCount());
  for (size_t s = 0; s < graph.VerticesCount(); ++s) {
    if (!visited[s]) DFSReverseRecursive(s, graph, visited, to_go);
  }
  return to_go;
}

void DFSCondense(size_t u, const IGraph& graph, std::vector<bool>& visited, std::vector<size_t>& component,
                 size_t current_component) {
  visited[u] = true;
  component[u] = current_component;
  for (int v : graph.FindAllAdjacentOut(u)) {
    if (!visited[v])
      DFSCondense(v, graph, visited, component, current_component);
  }
}

std::unique_ptr<IGraph> Condense(const IGraph& graph) {
  // Обход по обратным ребрам для Косарайю.
  std::vector<size_t> to_go = DFSReverse(graph);
  // Обход по прямым ребрам Косарайю, сохранение component: v -> номер компоненты
  std::vector<bool> visited(graph.VerticesCount());
  size_t current_component = 0;
  std::vector<size_t> component(graph.VerticesCount());
  for (int i = to_go.size() - 1; i >= 0; --i) {
    if (!visited[to_go[i]]) {
      DFSCondense(to_go[i], graph, visited, component, current_component);
      ++current_component;
    }
  }

  for (size_t i = 0; i < component.size(); ++i) {
    std::cout << i << "->" << component[i] << ", ";
  }
  std::cout << std::endl;

    // Создаем граф конденсации.
  std::unique_ptr<IGraph> condense = std::make_unique<SetGraph>(current_component);
  // Заполняем ребра.
  for (size_t u = 0; u < graph.VerticesCount(); ++u) {
    for (size_t v : graph.FindAllAdjacentOut(u)) {
      if (component[u] != component[v]) {
        condense->AddEdge(component[u], component[v]);
      }
    }
  }

  return condense;
}

int main1() {
  ListGraph lg(10);
  lg.AddEdge(6, 0);
  lg.AddEdge(3, 2);
  lg.AddEdge(2, 1);
  lg.AddEdge(2, 5);
  lg.AddEdge(1, 5);
  lg.AddEdge(3, 4);
  lg.AddEdge(4, 7);
  lg.AddEdge(7, 8);
  lg.AddEdge(8, 4);
  lg.AddEdge(5, 7);
  lg.AddEdge(1, 9);
  lg.AddEdge(9, 3);

  auto condense = Condense(lg);
  std::cout << condense->VerticesCount() << std::endl;
  for (size_t u = 0; u < condense->VerticesCount(); ++u) {
    for (size_t v : condense->FindAllAdjacentOut(u)) {
      std::cout << u << " " << v << std::endl;
    }
  }
  return 0;
}

class CompD {
 public:
  explicit CompD(const std::vector<int>& d) : d_(d) {}
  bool operator()(int a, int b) { return d_[a] > d_[b]; }

 private:
  const std::vector<int>& d_;
};

std::vector<int> Dijkstra(const std::vector<std::vector<int>>& matrix, int start) {
  std::vector<int> distances(matrix.size(), INT_MAX);
  distances[start] = 0;
  CompD comparer(distances);
  std::priority_queue<int, std::vector<int>, CompD> q(comparer);
  q.push(start);
  while (!q.empty()) {
    int u = q.top(); q.pop();
    for (int v = 0; v < matrix.size(); ++v) {
      int w = matrix[u][v];
      if (w >= 0) {
        if (distances[v] > distances[u] + w) {
          q.DecreaseKey(v, distances[u] + w);
          distances[v] = distances[u] + w;
        }
      }
    }
  }
  return distances;
}

/*
7
10
1 6 14
1 3 9
1 2 7
2 3 10
3 6 2
6 5 9
2 4 15
3 4 11
4 5 6
5 4 6
*/

int main() {
  int n; std::cin >> n;
  std::vector<std::vector<int>> matrix(n, std::vector<int>(n, -1));
  int e; std::cin >> e;
  for (int i = 0; i < e; ++i) {
    int u, v, w; std::cin >> u >> v >> w;
    matrix[u][v] = w;
  }
  int start; std::cin >> start;
  std::vector<int> distances = Dijkstra(matrix, start);
  return 0;
}