제출 #770063

#제출 시각아이디문제언어결과실행 시간메모리
770063mgl_diamondRobot (JOI21_ho_t4)C++17
34 / 100
3083 ms38084 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ii = pair<int, int>; #define foru(i, l, r) for(int i=(l); i<=(r); ++i) #define ford(i, l, r) for(int i=(l); i>=(r); --i) #define fore(x, v) for(auto &x : v) #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() #define fi first #define se second void setIO(string name) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (!name.empty()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } } struct edge { int u, v, c, p; edge (int _u=0, int _v=0, int _c=0, int _p=0) : u(_u), v(_v), c(_c), p(_p) {} int oth(int node) { return node ^ u ^ v; } }; struct state { ll cost; int u, need, i; state(ll _c=0, int _u=0, int _i=0, int _need=0) : cost(_c), u(_u), i(_i), need(_need) {} friend bool operator < (const state &a, const state &b) { return a.cost > b.cost; } }; const ll LINF = 1e15; const int N = 1e5+5; const int M = 2e5+5; int n, m; ll sum[M]; edge e[M]; vector<int> graph[N]; vector<ll> dp[N][2]; int get(int u, int i) { return lower_bound(all(graph[u]), i) - graph[u].begin(); } int main() { setIO(""); cin >> n >> m; foru(i, 1, m) { int u, v, c, p; cin >> u >> v >> c >> p; e[i] = edge(u, v, c, p); graph[u].push_back(i); graph[v].push_back(i); } foru(i, 1, n) { dp[i][0].resize(sz(graph[i]), LINF); dp[i][1].resize(sz(graph[i]), LINF); } priority_queue<state> pq; pq.push(state(0, 1, -1, -1)); while (!pq.empty()) { state at = pq.top(); pq.pop(); int u = at.u, lst = at.i, need = at.need; if (lst != -1 && dp[u][need][lst] != at.cost) continue; // cout << at.cost << " " << u << " " << lst << " " << need << "\n"; foru(i, 0, sz(graph[u])-1) { if (i==lst && need) continue; int idx = graph[u][i]; sum[e[idx].c] += e[idx].p; } foru(i, 0, sz(graph[u])-1) { if (i == at.i) continue; int idx = graph[u][i]; int v = e[idx].oth(u); int kth = get(v, idx); ll cost; // we change color of edge idx cost = at.cost + e[idx].p; if (dp[v][1][kth] > cost) { dp[v][1][kth] = cost; pq.push(state(cost, v, kth, 1)); } // we change color of its neighbor cost = at.cost + sum[e[idx].c] - e[idx].p; if (dp[v][0][kth] > cost) { dp[v][0][kth] = cost; pq.push(state(cost, v, kth, 0)); } } foru(i, 0, sz(graph[u])-1) { int idx = graph[u][i]; sum[e[idx].c] = 0; } } ll ans = LINF; foru(i, 0, sz(graph[n])-1) ans = min(ans, min(dp[n][0][i], dp[n][1][i])); cout << (ans == LINF ? -1 : ans); }

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

Main.cpp: In constructor 'state::state(ll, int, int, int)':
Main.cpp:31:16: warning: 'state::i' will be initialized after [-Wreorder]
   31 |   int u, need, i;
      |                ^
Main.cpp:31:10: warning:   'int state::need' [-Wreorder]
   31 |   int u, need, i;
      |          ^~~~
Main.cpp:32:3: warning:   when initialized here [-Wreorder]
   32 |   state(ll _c=0, int _u=0, int _i=0, int _need=0) : cost(_c), u(_u), i(_i), need(_need) {}
      |   ^~~~~
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...