Submission #650235

#TimeUsernameProblemLanguageResultExecution timeMemory
650235BungmintCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
13 ms19492 KiB
// Copyright © 2022 Youngmin Park. All rights reserved. #pragma GCC optimize("O3") //#pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; #pragma region TEMPLATE using ll = long long; using vi = vector<int>; using pii = pair<int, int>; using vpi = vector<pii>; using pll = pair<ll, ll>; using vl = vector<ll>; using vpl = vector<pll>; using ld = long double; template <typename T, size_t SZ> using ar = array<T, SZ>; template <typename T> using pqg = priority_queue<T, vector<T>, greater<T>>; #define all(v) (v).begin(), (v).end() #define pb push_back #define eb emplace_back #define sz(x) (int)(x).size() #define fi first #define se second #define lb lower_bound #define ub upper_bound constexpr int INF = 1e9; constexpr ll LINF = 1e18; const ld PI = acos((ld)-1.0); constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> constexpr bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <typename T> constexpr bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; } ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down #ifdef LOCAL #include "miscellaneous/debug.h" #else #define dbg(...) 42 #endif inline namespace RecursiveLambda { template <typename Fun> struct y_combinator_result { Fun fun_; template <typename T> explicit constexpr y_combinator_result(T &&fun) : fun_(forward<T>(fun)) {} template <typename... Args> constexpr decltype(auto) operator()(Args &&...args) const { return fun_(ref(*this), forward<Args>(args)...); } }; template <typename Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun)); } }; #pragma endregion TEMPLATE void solve() { int N, M; cin >> N >> M; vector<vpi> g(N); vi edge_color(M), edge_w(M); vl dist(N, LINF); vector<map<int, int>> colors(N); for (int i = 0; i < M; i++) { int u, v, c, p; cin >> u >> v >> c >> p; u--, v--; edge_color[i] = c; colors[u][c] += p; colors[v][c] += p; edge_w[i] = p; g[u].pb({v, i}); g[v].pb({u, i}); } dbg(colors); dist[0] = 0; pqg<pair<ll, int>> pq; pq.push({0, 0}); while (sz(pq)) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] != d) continue; for (auto &[v, id] : g[u]) { int w = min(edge_w[id], colors[u][edge_color[id]] - edge_w[id]); if (ckmin(dist[v], dist[u] + w)) { pq.push({dist[v], v}); } } } cout << (dist[N - 1] == LINF ? -1 : dist[N - 1]) << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int testcase = 1; // cin >> testcase; while (testcase--) { solve(); } #ifdef LOCAL cerr << "Time elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n"; #endif }

Compilation message (stderr)

commuter_pass.cpp:7: warning: ignoring '#pragma region TEMPLATE' [-Wunknown-pragmas]
    7 | #pragma region TEMPLATE
      | 
commuter_pass.cpp:66: warning: ignoring '#pragma endregion TEMPLATE' [-Wunknown-pragmas]
   66 | #pragma endregion TEMPLATE
      | 
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:46:18: warning: statement has no effect [-Wunused-value]
   46 | #define dbg(...) 42
      |                  ^~
commuter_pass.cpp:87:2: note: in expansion of macro 'dbg'
   87 |  dbg(colors);
      |  ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...