Submission #1197957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197957		guanex	Robot (JOI21_ho_t4)	C++20	0 / 100	44 ms	22596 KiB

Main

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<ll, int> pli;

#define INF 1e18
#define pb push_back

struct cmp {
    bool operator()(const vi &a, const vi &b) {
        return a[0] > b[0];
    }
};

void tc() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> ed(n);
    vector<vector<int>> edges(m);
    vector<unordered_map<int, ll>> color_cost(n);
    vector<vector<ll>> dp(m, vector<ll>(2, INF));
    vector<vector<bool>> vis(m, vector<bool>(2, false));

    for (int i = 0; i < m; ++i) {
        int u, v, c;
        ll p;
        cin >> u >> v >> c >> p;
        --u, --v;
        edges[i] = {u, v, c, (int)p};
        ed[u].pb(i);
        ed[v].pb(i);
        color_cost[u][c] += p;
        color_cost[v][c] += p;
    }

    using state = tuple<ll, int, int, int>; // (cost, edge idx, node_side (0/1), is_fat)
    priority_queue<state, vector<state>, greater<state>> pq;

    for (int e : ed[0]) {
        int u = edges[e][0], v = edges[e][1], c = edges[e][2];
        ll p = edges[e][3];

        int side = (u == 0) ? 0 : 1;
        ll single = p;
        ll group = color_cost[0][c] - p;

        if (single < dp[e][0]) {
            dp[e][0] = single;
            pq.emplace(single, e, side, 0);
        }

        if (group < dp[e][1]) {
            dp[e][1] = group;
            pq.emplace(group, e, side, 1);
        }
    }

    while (!pq.empty()) {
        auto [cost, idx, side, fat] = pq.top();
        pq.pop();

        if (vis[idx][fat] || dp[idx][fat] != cost) continue;
        vis[idx][fat] = true;

        int node = edges[idx][side];

        for (int e : ed[node]) {
            if (e == idx) continue;

            int next_side = (edges[e][0] == node) ? 0 : 1;
            int col = edges[e][2];
            ll p = edges[e][3];
            ll group = color_cost[node][col] - p;

            if (fat == 0 && edges[idx][2] == col)
                group -= edges[idx][3];

            group = max(group, 0LL);

            if (dp[e][0] > cost + p) {
                dp[e][0] = cost + p;
                pq.emplace(cost + p, e, next_side, 0);
            }

            if (dp[e][1] > cost + group) {
                dp[e][1] = cost + group;
                pq.emplace(cost + group, e, next_side, 1);
            }
        }
    }

    ll ans = INF;
    for (int e : ed[n - 1]) {
        ans = min({ans, dp[e][0], dp[e][1]});
    }

    cout << (ans == INF ? -1 : ans) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    tc();
    return 0;
}

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