Submission #702914

#	Time	Username	Problem	Language	Result	Execution time	Memory
702914		bebra	Robot (JOI21_ho_t4)	C++17	34 / 100	3100 ms	82108 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<vector<vector<ll>>> dist(n, vector<vector<ll>>(2));
    vector<vector<vector<bool>>> used(n, vector<vector<bool>>(2));
    const int SPECIAL = n;
    g[0].emplace_back(SPECIAL, m);
    for (int v = 0; v < n; ++v) {
        sort(g[v].begin(), g[v].end());
        for (int t = 0; t <= 1; ++t) {
            dist[v][t].assign(g[v].size(), INF);
            used[v][t].resize(g[v].size());
        }
    }

    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][t][idx]) continue;

        used[v][t][idx] = true;
        dist[v][t][idx] = 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][0][new_idx] && dist[u][0][new_idx] > curr_dist + cost[new_edge]) {
                dist[u][0][new_idx] = curr_dist + cost[new_edge];
                pq.emplace(dist[u][0][new_idx], 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][1][new_idx] && dist[u][1][new_idx] > curr_dist + new_cost) {
                dist[u][1][new_idx] = curr_dist + new_cost;
                pq.emplace(dist[u][1][new_idx], u, 1, new_idx);
            }

        }
    }

    ll ans = INF;
    for (int t = 0; t <= 1; ++t) {
        for (auto value : dist[n - 1][t]) {
            ans = min(ans, value);
        }
    }

    if (ans == INF) {
        cout << "-1\n";
    } else {
        cout << ans << '\n';
    }
    
    return 0;
}

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