Submission #2889218


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::pair<std::uint64_t, std::uint64_t>> costs(n);
  for (std::uint64_t i = 0; i < n; ++i) {
    costs[i] = std::make_pair(yen_costs[i] + snuuk_costs[i], i);
  }
  std::sort(costs.begin(), costs.end(), std::greater<std::pair<std::uint64_t, std::uint64_t>>());
  for (std::uint64_t i = 0; i < n; ++i) {
    std::cout << 1000000000000000 - std::get<0>(costs.back()) << std::endl;
    while (i + 1 > std::get<1>(costs.back())) {
      costs.pop_back();
    }
  }
  return 0;
}

Submission Info

Submission Time
Task D - Saving Snuuk
User anqooqie
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3403 Byte
Status AC
Exec Time 489 ms
Memory 40960 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 56
Set Name Test Cases
Sample sampleRnd.txt, sampleT.txt
All 00yorimichi.txt, 11_0.txt, 11_1.txt, 11_2.txt, 11_3.txt, 11_4.txt, 1n1m1.txt, 1oo_0.txt, 1oo_1.txt, 1oo_2.txt, 1oo_3.txt, 1oo_4.txt, dangou_0.txt, dangou_1.txt, dangou_2.txt, dangou_3.txt, dangou_4.txt, edge.txt, high_0.txt, high_1.txt, high_2.txt, high_3.txt, high_4.txt, low_0.txt, low_1.txt, low_2.txt, low_3.txt, low_4.txt, oo1_0.txt, oo1_1.txt, oo1_2.txt, oo1_3.txt, oo1_4.txt, path_0.txt, path_1.txt, path_2.txt, path_3.txt, path_4.txt, path_5.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sampleRnd.txt, sampleT.txt, slast_0.txt, slast_1.txt, slast_2.txt, slast_3.txt, slast_4.txt, tlast_0.txt, tlast_1.txt, tlast_2.txt, tlast_3.txt, tlast_4.txt
Case Name Status Exec Time Memory
00yorimichi.txt AC 370 ms 40960 KB
11_0.txt AC 395 ms 31736 KB
11_1.txt AC 300 ms 22000 KB
11_2.txt AC 312 ms 23928 KB
11_3.txt AC 488 ms 39676 KB
11_4.txt AC 437 ms 34556 KB
1n1m1.txt AC 377 ms 31116 KB
1oo_0.txt AC 386 ms 30708 KB
1oo_1.txt AC 387 ms 31732 KB
1oo_2.txt AC 230 ms 20976 KB
1oo_3.txt AC 391 ms 33012 KB
1oo_4.txt AC 383 ms 31736 KB
dangou_0.txt AC 235 ms 17016 KB
dangou_1.txt AC 291 ms 23544 KB
dangou_2.txt AC 374 ms 32632 KB
dangou_3.txt AC 158 ms 12536 KB
dangou_4.txt AC 467 ms 40696 KB
edge.txt AC 450 ms 40832 KB
high_0.txt AC 197 ms 15480 KB
high_1.txt AC 264 ms 20592 KB
high_2.txt AC 454 ms 37368 KB
high_3.txt AC 30 ms 3072 KB
high_4.txt AC 323 ms 29052 KB
low_0.txt AC 219 ms 20468 KB
low_1.txt AC 239 ms 22260 KB
low_2.txt AC 379 ms 34172 KB
low_3.txt AC 320 ms 31484 KB
low_4.txt AC 250 ms 23412 KB
oo1_0.txt AC 415 ms 34936 KB
oo1_1.txt AC 346 ms 28916 KB
oo1_2.txt AC 300 ms 25588 KB
oo1_3.txt AC 292 ms 23412 KB
oo1_4.txt AC 312 ms 25208 KB
path_0.txt AC 394 ms 34944 KB
path_1.txt AC 380 ms 34816 KB
path_2.txt AC 175 ms 17152 KB
path_3.txt AC 232 ms 21632 KB
path_4.txt AC 121 ms 11904 KB
path_5.txt AC 353 ms 30592 KB
rnd_0.txt AC 404 ms 31352 KB
rnd_1.txt AC 475 ms 37884 KB
rnd_2.txt AC 67 ms 6652 KB
rnd_3.txt AC 440 ms 35576 KB
rnd_4.txt AC 311 ms 25716 KB
sampleRnd.txt AC 1 ms 256 KB
sampleT.txt AC 1 ms 256 KB
slast_0.txt AC 384 ms 30708 KB
slast_1.txt AC 277 ms 23156 KB
slast_2.txt AC 445 ms 37368 KB
slast_3.txt AC 325 ms 25716 KB
slast_4.txt AC 431 ms 32760 KB
tlast_0.txt AC 302 ms 22900 KB
tlast_1.txt AC 374 ms 29176 KB
tlast_2.txt AC 425 ms 36088 KB
tlast_3.txt AC 468 ms 39804 KB
tlast_4.txt AC 489 ms 39804 KB