제출 #874850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874850		tvladm2009	Robot (JOI21_ho_t4)	C++17	100 / 100	753 ms	84544 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge {
    int to;
    int c;
    ll p;
};

const int N = 1e5 + 7;
const ll INF = 1e18;

int n, m;
map<int, vector<Edge>> g[N];
ll dp[N];
map<int, ll> dp2[N], psum[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        g[a][c].push_back({b, c, p});
        g[b][c].push_back({a, c, p});
        psum[a][c] += p;
        psum[b][c] += p;
    }
    for (int i = 1; i <= n; ++i) {
        dp[i] = INF;
    }
    priority_queue<tuple<ll, int, int>> pq;
    dp[1] = 0;
    pq.push({0, 1, 0});
    while (!pq.empty()) {
        ll cost;
        int u, c;
        tie(cost, u, c) = pq.top();
        pq.pop();
        if (c) {
            if (dp2[u][c] != -cost) {
                continue;
            }
            for (auto v : g[u][c]) {
                // we cant flip
                ll relax = psum[u][c] - v.p;
                if (relax - cost < dp[v.to]) {
                    dp[v.to] = relax - cost;
                    pq.push({-dp[v.to], v.to, 0});
                }
            }
        } else {
            if (dp[u] != -cost) {
                continue;
            }
            for (auto v : g[u]) {
                for (auto edg : v.second) {
                    // we dont flip j
                    ll relax = psum[u][edg.c] - edg.p - cost;
                    if (relax < dp[edg.to]) {
                        dp[edg.to] = relax;
                        pq.push({-dp[edg.to], edg.to, 0});
                    }
                    // we flip j but not another edge of the same colour
                    relax = edg.p - cost;
                    if (relax < dp[edg.to]) {
                        dp[edg.to] = relax;
                        pq.push({-dp[edg.to], edg.to, 0});
                    }
                    // we flip j and another edge of the same colour
                    relax = -cost;
                    if (!dp2[edg.to].count(edg.c) || relax < dp2[edg.to][edg.c]) {
                        dp2[edg.to][edg.c] = relax;
                        pq.push({-dp2[edg.to][edg.c], edg.to, edg.c});
                    }
                }
            }
        }
    }
    if (dp[n] == INF) {
        dp[n] = -1;
    }
    cout << dp[n];
    return 0;
}

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