結果
問題 | No.807 umg tours |
ユーザー | Tiramister |
提出日時 | 2019-03-22 21:54:30 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 545 ms / 4,000 ms |
コード長 | 5,011 bytes |
コンパイル時間 | 1,273 ms |
コンパイル使用メモリ | 119,132 KB |
実行使用メモリ | 45,136 KB |
最終ジャッジ日時 | 2023-08-15 11:56:10 |
合計ジャッジ時間 | 7,752 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,384 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 300 ms
32,044 KB |
testcase_12 | AC | 298 ms
24,344 KB |
testcase_13 | AC | 424 ms
33,412 KB |
testcase_14 | AC | 166 ms
16,072 KB |
testcase_15 | AC | 127 ms
13,512 KB |
testcase_16 | AC | 441 ms
34,992 KB |
testcase_17 | AC | 538 ms
42,480 KB |
testcase_18 | AC | 545 ms
41,520 KB |
testcase_19 | AC | 522 ms
38,964 KB |
testcase_20 | AC | 311 ms
22,612 KB |
testcase_21 | AC | 314 ms
23,064 KB |
testcase_22 | AC | 132 ms
11,828 KB |
testcase_23 | AC | 97 ms
10,108 KB |
testcase_24 | AC | 325 ms
34,500 KB |
testcase_25 | AC | 522 ms
45,136 KB |
ソースコード
// IO library #include <cstdio> #include <iomanip> #include <ios> #include <iostream> // algorithm library #include <algorithm> #include <cmath> #include <numeric> #include <random> // contancer library #include <bitset> #include <deque> #include <map> #include <queue> #include <set> #include <string> #include <tuple> #include <vector> #include <functional> #include <limits> using ll = long long; using ld = long double; /* ----- Output Functions for Debugging ----- */ template <class T> std::ostream& operator<<(std::ostream& os, std::vector<T> v); template <class T> std::ostream& operator<<(std::ostream& os, std::set<T> v); template <class L, class R> std::ostream& operator<<(std::ostream& os, std::pair<L, R> p); template <class K, class T> std::ostream& operator<<(std::ostream& os, std::map<K, T> v); template <class T> std::ostream& operator<<(std::ostream& os, std::queue<T> q); template <class T> std::ostream& operator<<(std::ostream& os, std::priority_queue<T> q); template <class T> std::ostream& operator<<(std::ostream& os, std::vector<T> v) { os << "["; for (auto vv : v) os << vv << ","; return os << "]"; } template <class T> std::ostream& operator<<(std::ostream& os, std::set<T> v) { os << "{"; for (auto vv : v) os << vv << ","; return os << "}"; } template <class L, class R> std::ostream& operator<<(std::ostream& os, std::pair<L, R> p) { return os << "(" << p.first << "," << p.second << ")"; } template <class K, class T> std::ostream& operator<<(std::ostream& os, std::map<K, T> v) { os << "{"; for (auto vv : v) os << vv << ","; return os << "}"; } template <class T> std::ostream& operator<<(std::ostream& os, std::queue<T> q) { os << "["; while (!q.empty()) { os << q.front() << ","; q.pop(); } return os << "]"; } template <class T> std::ostream& operator<<(std::ostream& os, std::priority_queue<T> q) { os << "{"; while (!q.empty()) { os << q.top() << ","; q.pop(); } return os << "}"; } /* ----- Short Functions ----- */ template <class T> T Vec(T v) { return v; } template <class T, class... Ts> auto Vec(size_t l, Ts... ts) { return std::vector<decltype(Vec<T>(ts...))>(l, Vec<T>(ts...)); } template <class T> inline T sq(T a) { return a * a; } template <class T> inline T iceil(T n, T d) { return (n + d - 1) / d; } template <class T> T gcd(T a, T b) { while (b > 0) { a %= b; swap(a, b); } return a; } template <class T, class U> T ipow(T b, U n) { T ret = 1; while (n > 0) { if (n & 1) ret *= b; n >>= 1; b *= b; } return ret; } // 0-indexed template <class T, class U> inline T kthbit(T a, U k) { return (a >> k) & 1; } template <class T, class U> inline T mask(T a, U k) { return a & ((1 << k) - 1); } /* ----- class ----- */ template <class T> struct Edge { int from, to; T cost; Edge(int from = -1, int to = -1, T cost = 1) : from(from), to(to), cost(cost){}; bool operator<(const Edge<T>& e) const { return this->cost < e.cost; } bool operator>(const Edge<T>& e) const { return this->cost > e.cost; } }; template <class T = int> class Graph { public: explicit Graph(int N = 0) : size(N) { path.resize(size); } void span(int u, int v, T cost = 1) { path[u].push_back(Edge<T>(u, v, cost)); } std::vector<Edge<T>> operator[](int v) const { return path[v]; } int size; std::vector<std::vector<Edge<T>>> path; }; /* ----- Constants ----- */ // const int INF = 1 << 25; // const ll INF = 1LL << 50; // const ld PI = acos(-1); // const ld EPS = 1e-10; // mt19937 mt(ll(time(0))); const ll INF = std::numeric_limits<ll>::max(); template <class T> std::vector<T> dijkstra(const Graph<T>& graph, int s) { std::vector<T> dist(graph.size, INF); dist[s] = dist[s + graph.size / 2] = 0; std::priority_queue<std::pair<int, T>, std::vector<std::pair<int, T>>, std::greater<std::pair<int, T>>> que; que.emplace(0, s); que.emplace(0, s + graph.size / 2); while (!que.empty()) { int v; T d; std::tie(d, v) = que.top(); que.pop(); if (d > dist[v]) continue; for (const auto& e : graph[v]) { if (dist[e.to] <= dist[v] + e.cost) continue; dist[e.to] = dist[v] + e.cost; que.emplace(dist[e.to], e.to); } } return dist; } int main() { int N, M; std::cin >> N >> M; Graph<ll> graph(N * 2); for (int i = 0; i < M; ++i) { int u, v; ll c; std::cin >> u >> v >> c; --u, --v; graph.span(u, v, c); graph.span(v, u, c); graph.span(u, v + N, 0); graph.span(v, u + N, 0); graph.span(u + N, v + N, c); graph.span(v + N, u + N, c); } auto dist = dijkstra<ll>(graph, 0); // std::cerr << dist << std::endl; for (int v = 0; v < N; ++v) { std::cout << dist[v] + dist[v + N] << std::endl; } return 0; }