Submission #702929

#	Time	Username	Problem	Language	Result	Execution time	Memory
702929		bebra	Robot (JOI21_ho_t4)	C++17	0 / 100	490 ms	33820 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define dbg(x) cerr << #x << ": " << x << endl;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> g(n);
    vector<int> color(m + 1);
    vector<int> cost(m + 1);
    vector<map<int, ll>> color_cost(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        cin >> color[i] >> cost[i];
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
        color_cost[u][color[i]] += cost[i];
        color_cost[v][color[i]] += cost[i];
    }

    const ll INF = 1e18;

    vector<ll> dist(n, INF);
    vector<bool> used(n);

    const int SPECIAL = n;
    g[0].emplace_back(SPECIAL, m);

    for (int v = 0; v < n; ++v) {
        sort(g[v].begin(), g[v].end());
    }

    priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pq;
    pq.emplace(0, 0, 0, g[0].size() - 1);
    while (!pq.empty()) {
        auto [curr_dist, v, t, idx] = pq.top();
        pq.pop();
        if (used[v]) continue;

        used[v] = true;
        dist[v] = curr_dist;

        int prev_edge = g[v][idx].second;
        for (const auto& [u, new_edge] : g[v]) {
            if (u == SPECIAL) continue;
            if (new_edge == prev_edge) continue;
            
            int new_idx = lower_bound(g[u].begin(), g[u].end(), make_pair(v, -1)) - g[u].begin();

            if (!used[u] && dist[u] > curr_dist + cost[new_edge]) {
                dist[u] = curr_dist + cost[new_edge];
                pq.emplace(dist[u], u, 0, new_idx);
            }

            if (t == 1 && color[new_edge] == color[prev_edge]) continue;

            ll new_cost = color_cost[v][color[new_edge]] - cost[new_edge];
            if (t == 0 && color[new_edge] == color[prev_edge]) new_cost -= cost[prev_edge];

            if (!used[u] && dist[u] > curr_dist + new_cost) {
                dist[u] = curr_dist + new_cost;
                pq.emplace(dist[u], u, 1, new_idx);
            }
        }
    }


    if (!used[n - 1]) {
        cout << "-1\n";
    } else {
        cout << dist[n - 1] << '\n';
    }
    
    return 0;
}

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