This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub knshnb/competitive_library
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/0423" #include <bits/stdc++.h> // clang-format off using Int = long long; #define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io; #ifndef dump #define dump(...) #endif // clang-format on /** * author: knshnb * created: Mon Apr 27 01:47:13 JST 2020 **/ #define CALL_FROM_TEST #include "../../src/Graph/Dijkstra.hpp" #undef CALL_FROM_TEST signed main() { Int n, R; std::cin >> n >> R; Dijkstra<Int> dj(n + 1); std::vector<Int> e(n); REP(i, n) { Int t; std::cin >> t >> e[i]; dj.add_edge(n, i, t); } REP(_, R) { Int a, b, c; std::cin >> a >> b >> c; a--, b--; dj.add_edge(b, a, c - 1); } auto dist = dj.run(n); Int ans = 0; REP(i, n) ans += dist[i] * e[i]; std::cout << ans << std::endl; }
#line 1 "test/aoj/0423.test.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/0423" #include <bits/stdc++.h> // clang-format off using Int = long long; #define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io; #ifndef dump #define dump(...) #endif // clang-format on /** * author: knshnb * created: Mon Apr 27 01:47:13 JST 2020 **/ #define CALL_FROM_TEST #line 1 "src/Graph/Dijkstra.hpp" template <class T, bool directed = true> struct Dijkstra { struct Edge { int to; T cost; }; std::vector<std::vector<Edge>> g; Dijkstra(int n) : g(n) {} void add_edge(int u, int v, T cost) { g[u].push_back({v, cost}); if (!directed) g[v].push_back({u, cost}); } std::vector<T> run(int s) { std::vector<T> dist(g.size(), std::numeric_limits<T>::max() / 2); // {d, v} std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> q; q.push({0, s}); while (!q.empty()) { std::pair<T, int> p = q.top(); q.pop(); int v = p.second; if (dist[v] <= p.first) continue; dist[v] = p.first; for (const Edge& e : g[v]) { if (dist[e.to] <= p.first + e.cost) continue; // 定数倍枝刈り q.emplace(p.first + e.cost, e.to); } } return dist; } }; #line 19 "test/aoj/0423.test.cpp" #undef CALL_FROM_TEST signed main() { Int n, R; std::cin >> n >> R; Dijkstra<Int> dj(n + 1); std::vector<Int> e(n); REP(i, n) { Int t; std::cin >> t >> e[i]; dj.add_edge(n, i, t); } REP(_, R) { Int a, b, c; std::cin >> a >> b >> c; a--, b--; dj.add_edge(b, a, c - 1); } auto dist = dj.run(n); Int ans = 0; REP(i, n) ans += dist[i] * e[i]; std::cout << ans << std::endl; }