Submission #2889204

---

Source Code Expand

#include <queue>
#include <cstddef>
#include <utility>
#include <vector>
#include <limits>
#include <unordered_map>
#include <cassert>

namespace tools {
  template <typename T> class dijkstra {
  private:
    const std::size_t start_node;
    std::vector<T> distances;
    std::vector<std::size_t> prev_nodes;
    std::priority_queue<std::pair<T, std::size_t>, std::vector<std::pair<T, std::size_t>>, std::greater<std::pair<T, std::size_t>>> tasks;
    std::vector<std::unordered_map<std::size_t, T>> edges;

  public:
    static constexpr std::size_t NONE = std::numeric_limits<std::size_t>::max();

    dijkstra(const std::size_t node_count, const std::size_t start_node) :
      start_node(start_node),
      distances(node_count),
      prev_nodes(node_count),
      tasks(),
      edges(node_count) {
      assert(start_node < node_count);
    }

    void add_edge(const std::size_t from, const std::size_t to, const T distance) {
      this->edges[from].insert(std::make_pair(to, distance));
    }

    std::vector<T> calc() {
      this->distances.assign(this->distances.size(), std::numeric_limits<T>::max());
      this->prev_nodes.assign(this->prev_nodes.size(), std::size_t(NONE));
      this->tasks.push(std::make_pair(0, this->start_node));
      while (!this->tasks.empty()) {
        const std::pair<T, std::size_t> task = this->tasks.top();
        this->tasks.pop();
        const T& distance = std::get<0>(task);
        const std::size_t& target_node = std::get<1>(task);
        if (this->distances[target_node] != std::numeric_limits<T>::max()) {
          // old task for already visited node
          continue;
        }
        this->distances[target_node] = distance;
        for (const std::pair<std::size_t, T>& edge : this->edges[target_node]) {
          const std::size_t& next_node = std::get<0>(edge);
          const T new_distance = distance + std::get<1>(edge);
          if (new_distance < this->distances[next_node]) {
            this->prev_nodes[next_node] = target_node;
            this->tasks.push(std::make_pair(new_distance, next_node));
          }
        }
      }
      return this->distances;
    }
  };
}

#include <iostream>
#include <cstdint>
#include <algorithm>

int main() {
  std::uint64_t n, m, s, t;
  std::cin >> n >> m >> s >> t;
  tools::dijkstra<std::uint64_t> yen_dijkstra(n, s - 1);
  tools::dijkstra<std::uint64_t> snuuk_dijkstra(n, t - 1);
  std::uint64_t u, v, a, b;
  for (std::uint64_t i = 0; i < m; ++i) {
    std::cin >> u >> v >> a >> b;
    yen_dijkstra.add_edge(u - 1, v - 1, a);
    yen_dijkstra.add_edge(v - 1, u - 1, a);
    snuuk_dijkstra.add_edge(u - 1, v - 1, b);
    snuuk_dijkstra.add_edge(v - 1, u - 1, b);
  }
  std::vector<std::uint64_t> yen_costs = yen_dijkstra.calc();
  std::vector<std::uint64_t> snuuk_costs = snuuk_dijkstra.calc();
  std::vector<std::uint64_t> costs(n);
  for (std::uint64_t i = 0; i < n; ++i) {
    costs[i] = yen_costs[i] + snuuk_costs[i];
  }
  for (std::uint64_t i = 0; i < n; ++i) {
    std::cout << 1000000000000000 - *std::min_element(costs.begin(), costs.end()) << std::endl;
    costs[i] = std::numeric_limits<std::uint64_t>::max();
  }
  return 0;
}

Submission Info

Judge Result