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 |
|
|
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 |