Submission #892228

#TimeUsernameProblemLanguageResultExecution timeMemory
892228GhettoRobot (JOI21_ho_t4)C++17
34 / 100
3101 ms155232 KiB
/* When state exploding/DPing, make sure to optimise each individual state and not prematurely optimise. Not sure why this is still to slow, hashmaps?? */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; using lint = long long; const int MAX_N = 1e5 + 5; const lint INF = 1e18 + 5; int n, m; struct Edge { int node, col; lint cost; }; vector<Edge> adj[MAX_N]; gp_hash_table<int, int> adj_ind[MAX_N]; gp_hash_table<int, lint> col_cost_sum[MAX_N]; gp_hash_table<int, lint> min_dist[MAX_N]; gp_hash_table<int, bool> seen[MAX_N]; struct State { int node, prev_edge; // -1 at beginning or if we didn't take directly lint dist; bool operator<(State other) const { return dist > other.dist; } }; priority_queue<State> order; lint dijk() { for (int i = 1; i <= n; i++) { min_dist[i][-1] = INF; for (int j = 0; j < adj[i].size(); j++) { min_dist[i][j] = INF; } } min_dist[1][-1] = 0; order.push({1, -1, 0}); lint ans = INF; while (order.size()) { int u = order.top().node, prev_ind = order.top().prev_edge; lint dist = order.top().dist; order.pop(); if (seen[u][prev_ind]) continue; seen[u][prev_ind] = true; if (u == n) ans = min(ans, dist); if (prev_ind != -1) col_cost_sum[u][adj[u][prev_ind].col] -= adj[u][prev_ind].cost; for (auto& v : adj[u]) { if (prev_ind != -1 && v.node == adj[u][prev_ind].node) continue; lint new_dist1 = dist + v.cost; int new_ind1 = adj_ind[v.node][u]; if (new_dist1 < min_dist[v.node][new_ind1]) { min_dist[v.node][new_ind1] = new_dist1; order.push({v.node, new_ind1, new_dist1}); } lint new_dist2 = dist + col_cost_sum[u][v.col] - v.cost; int new_ind2 = -1; if (new_dist2 < min_dist[v.node][new_ind2]) { min_dist[v.node][new_ind2] = new_dist2; order.push({v.node, new_ind2, new_dist2}); } } if (prev_ind != -1) col_cost_sum[u][adj[u][prev_ind].col] += adj[u][prev_ind].cost; } return (ans == INF) ? -1 : ans; } int main() { // freopen("robot.in", "r", stdin); // freopen("robot.out", "w", stdout); cin.sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, col; cin >> u >> v >> col; lint cost; cin >> cost; adj[u].push_back({v, col, cost}); adj_ind[u][v] = adj[u].size() - 1; adj[v].push_back({u, col, cost}); adj_ind[v][u] = adj[v].size() - 1; col_cost_sum[u][col] += cost; col_cost_sum[v][col] += cost; } cout << dijk() << '\n'; }

Compilation message (stderr)

Main.cpp: In function 'lint dijk()':
Main.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int j = 0; j < adj[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...