제출 #406582

#제출 시각아이디문제언어결과실행 시간메모리
406582FalconRobot (JOI21_ho_t4)C++17
34 / 100
3083 ms153484 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it) #define rep(i, N) for(int i = 0; i < (N); ++i) #define rrep(i, N) for(int i = (N) - 1; i >= 0; --i) #define rep1(i, N) for(int i = 1; i <= (N); ++i) #define rep2(i, s, e) for(int i = (s); i <= (e); ++i) #ifdef DEBUG #define debug(x...) { \ ++dbg::depth; \ string dbg_vals = dbg::to_string(x); \ --dbg::depth; \ dbg::fprint(__func__, __LINE__, #x, dbg_vals); \ } #define light_debug(x) { \ dbg::light = true; \ dbg::dout << __func__ << ":" << __LINE__; \ dbg::dout << " " << #x << " = " << x << endl; \ dbg::light = false; \ } #else #define debug(x...) 42 #define light_debug(x) 42 #endif using ll = long long; template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; struct edge { int x, c; long long p; }; vector<edge> edges(M); vector<vector<int>> adj(N); vector<map<int, long long>> c_sum(N); rep(i, M) { edge& e{edges[i]}; int u, v; cin >> u >> v >> e.c >> e.p; --u, --v, --e.c; e.x = u ^ v; c_sum[u][e.c] += e.p; c_sum[v][e.c] += e.p; adj[u].push_back(i); adj[v].push_back(i); } priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq; vector<map<int, long long>> dist(N); pq.push({0, 0, -1}); auto add = [&](int v, int i, long long d) { if(dist[v].count(i)) return; else pq.push({d, v, i}); }; while(!pq.empty()) { auto [d, u, j] = pq.top(); pq.pop(); if(dist[u].count(j)) continue; dist[u][j] = d; for(int i: adj[u]) { if(i == j) continue; edge e{edges[i]}; int v{e.x ^ u}; if(j == -1 || edges[j].c != e.c) { add(v, i, d + e.p); add(v, -1, d + c_sum[u][e.c] - e.p); } else { add(v, i, d + e.p); add(v, -1, d + c_sum[u][e.c] - e.p - edges[j].p); } } } debug(dist); long long ans{-1}; for(auto [_, d]: dist.back()) { if(ans == -1 || ans > d) ans = d; } cout << ans << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl; #endif return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
Main.cpp:101:5: note: in expansion of macro 'debug'
  101 |     debug(dist);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...