Submission #892223

#	Time	Username	Problem	Language	Result	Execution time	Memory
892223		Ghetto	Robot (JOI21_ho_t4)	C++17	34 / 100	3053 ms	120800 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];
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_set<int> 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].count(prev_ind)) continue;
        seen[u].insert(prev_ind);
        if (u == n) {
            ans = min(ans, dist);
            continue;
        }

        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: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: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42