Submission #892193

#	Time	Username	Problem	Language	Result	Execution time	Memory
892193		Ghetto	Robot (JOI21_ho_t4)	C++17	0 / 100	2092 ms	123636 KiB

Main

#include <bits/stdc++.h>
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];
unordered_map<int, int> adj_ind[MAX_N];

unordered_map<int, lint> col_cost_sum[MAX_N];
unordered_map<int, lint> min_dist[MAX_N];
unordered_map<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;
        order.pop();

        if (seen[u][prev_ind]) continue;
        seen[u][prev_ind] = true;
        if (u == n) ans = min(ans, min_dist[u][prev_ind]);

        //cout << u << " " << prev_ind << " " << min_dist[u][prev_ind] << endl;

        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_dist = 0; int new_ind = 0;
            if (v.cost < col_cost_sum[u][v.col] - v.cost) {
                new_dist = min_dist[u][prev_ind] + v.cost;
                new_ind = adj_ind[v.node][u];
            } else {
                new_dist = min_dist[u][prev_ind] + col_cost_sum[u][v.col] - v.cost;
                new_ind = -1;
            }
            if (new_dist >= min_dist[v.node][new_ind]) continue;

            min_dist[v.node][new_ind] = new_dist;
            order.push({v.node, new_ind, new_dist});
        }
        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 >> 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;
    }

    // for (int i = 1; i <= n; i++) {
    //     cout << i << ": ";
    //     for (auto& j : adj[i]) cout << j.node << " ";
    //     cout << '\n';
    // }

    cout << dijk() << '\n';
}

Compilation message (stderr)

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

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42