제출 #626751

#제출 시각아이디문제언어결과실행 시간메모리
626751colossal_pepeRobot (JOI21_ho_t4)C++17
34 / 100
3062 ms47696 KiB
#include <iostream> #include <vector> #include <queue> #include <map> using namespace std; using ll = long long; const ll INF = 1e18; int n, m; vector<int> a, b, c; vector<ll> p; vector<vector<int>> g; ll solve() { priority_queue<tuple<ll, int, bool>> pq; vector<vector<ll>> dp(2 * m, vector<ll>(2, -INF)); dp[m - 1][0] = 0; pq.push({0, m - 1, 0}); while (not pq.empty()) { auto [d, e_prev, changed] = pq.top(); pq.pop(); if (dp[e_prev][changed] != d) continue; int u = b[e_prev]; // cout << "! " << d << ' ' << e_prev << ' ' << u << '\n'; map<int, ll> cost; if (changed) cost[c[e_prev]] -= p[e_prev]; for (int e_nxt : g[u]) { cost[c[e_nxt]] += p[e_nxt]; } for (int e_nxt : g[u]) { ll incur = min(0ll, cost[c[e_nxt]] - p[e_nxt]); if (d + incur > dp[e_nxt][0]) { dp[e_nxt][0] = d + incur; pq.push({dp[e_nxt][0], e_nxt, 0}); } incur = p[e_nxt]; if (d + incur > dp[e_nxt][1]) { dp[e_nxt][1] = d + incur; pq.push({dp[e_nxt][1], e_nxt, 1}); } } } ll ans = -INF; for (int i = 0; i < 2 * m; i++) { if (b[i] == n - 1) { // cout << -dp[i][0] << ' ' << -dp[i][1] << '\n'; ans = max(ans, max(dp[i][0], dp[i][1])); } } return (ans != -INF ? -ans : -1); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; m++; g.resize(n); a.resize(2 * m), b.resize(2 * m), c.resize(2 * m), p.resize(2 * m); for (int i = 0; i < m - 1; i++) { cin >> a[i] >> b[i] >> c[i] >> p[i]; a[i]--, b[i]--; p[i] *= -1; a[i + m] = b[i]; b[i + m] = a[i]; c[i + m] = c[i]; p[i + m] = p[i]; g[a[i]].push_back(i); g[b[i]].push_back(i + m); } cout << solve() << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...