Submission #1273114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273114		trantrungkein	Robot (JOI21_ho_t4)	C++20	34 / 100	3096 ms	65408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int N = 2e5 + 7;

vector<tuple<int,int,long long>> g[N];
unordered_map<int,long long> dp2[N], sum[N];
long long dp[N];
int n, m;

struct Node {
    int u, c;
    long long dist;
    bool operator < (const Node &other) const {
        return dist > other.dist; // min-heap
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        long long p;
        cin >> u >> v >> c >> p;
        g[u].push_back({v, c, p});
        g[v].push_back({u, c, p});
        sum[u][c] += p;
        sum[v][c] += p;
    }

    fill(dp + 1, dp + n + 1, INF);
    dp[1] = 0;

    priority_queue<Node> q;
    q.push({1, 0, 0});

    while (!q.empty()) {
        auto [u, c, dist] = q.top(); q.pop();

        if (c != 0) {
            if (dp2[u][c] != dist) continue;
            for (auto [v, color, p] : g[u]) if (color == c) {
                long long value = dist + sum[u][color] - p;
                if (dp[v] > value) {
                    dp[v] = value;
                    q.push({v, 0, dp[v]});
                }
            }
        } else {
            if (dp[u] != dist) continue;
            for (auto [v, color, p] : g[u]) {
                // Case 1: tô cả nhóm
                long long value = dist + sum[u][color] - p;
                if (dp[v] > value) {
                    dp[v] = value;
                    q.push({v, 0, dp[v]});
                }
                // Case 2: tô riêng
                value = dist + p;
                if (dp[v] > value) {
                    dp[v] = value;
                    q.push({v, 0, dp[v]});
                }
                // Case 3: dồn nợ
                if (!dp2[v].count(color) || dp2[v][color] > dist) {
                    dp2[v][color] = dist;
                    q.push({v, color, dp2[v][color]});
                }
            }
        }
    }

    cout << (dp[n] == INF ? -1 : dp[n]);
}

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