Submission #773850

#	Time	Username	Problem	Language	Result	Execution time	Memory
773850		mcdx9524	Robot (JOI21_ho_t4)	C++17	34 / 100	3065 ms	146384 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int long long

const long long inf = 1e18 + 7;

struct edge {
    int to, color;
    long long price;
    int global_index;
};

struct info {
    int to;
    long long cost;
    int index, global_index;
};

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <vector <edge> > g(n);
    vector <edge> edges;
    for (int i = 0; i < m; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        a--, b--;
        g[a].push_back({b, c, p, i});
        g[b].push_back({a, c, p, i});
        edges.push_back({-1, c, p, i});
    }
    map <int, int> total_price; 
    vector <vector <info> > cg(n);
    map <pair <int, int>, int> global;
    map <pair <int, int>, int> global_rev;
    map <int, int> global_price;
    for (int i = 0; i < n; i++) {
        for (auto [to, color, price, _] : g[i]) {
            total_price[color] += price;
        }
        int index = 0;
        for (auto [to, color, price, global_index] : g[i]) {
            global[{i, index}] = global_index;
            global_rev[{i, global_index}] = index;
            global_price[global_index] = price;
            cg[i].push_back({to, total_price[color] - price, -1, global_index});
            cg[i].push_back({to, price, index, global_index});
            index++;
        }
        for (auto [to, color, price, _] : g[i]) {
            total_price[color] -= price;
        }
    }
    priority_queue <tuple <long long, int, int> > q;
    q.push({0, 0, -1});
    vector <vector <long long> > d(n);
    for (int i = 0; i < n; i++) {
        d[i].resize((int) g[i].size() + 1, inf);
    }
    d[0][0] = 0;
    while (!q.empty()) {
        auto [cost, v, id] = q.top();
        q.pop();
        if (-cost > d[v][id + 1]) {
            continue;
        }
        for (int i = 0; i < (int) cg[v].size(); i++) {
            auto [to, new_cost, index, global_index] = cg[v][i];
            int actual_index = -1;
            if (index != -1) {               
                actual_index = global_rev[{to, global_index}];
            } else if (id != -1) {
                int global_id = global[{v, id}];
                int incoming_color = edges[global_id].color;
                int outgoing_color = edges[global_index].color;
                if (incoming_color == outgoing_color) {
                    new_cost -= edges[global_id].price;
                }
            }
            if (d[to][actual_index + 1] > d[v][id + 1] + new_cost) {
                d[to][actual_index + 1] = d[v][id + 1] + new_cost;
                q.push({-d[to][actual_index + 1], to, actual_index});
            }
        }
    }
    ll mn = inf;
    for (int i = 0; i < (int) g[n - 1].size() + 1; i++) {
        mn = min(mn, d[n - 1][i]);
    }
    cout << (mn == inf ? -1 : mn) << '\n';
    return 0;
}

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