제출 #1273662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273662		ericl23302	Robot (JOI21_ho_t4)	C++20	100 / 100	928 ms	79324 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

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

    int n, m;
    cin >> n >> m;

    vector<map<int, vector<pair<ll, pair<int, int>>>>> adjacency(n + 1);
    vector<map<int, ll>> sumOfColour(n + 1), dp(n + 1);
    vector<ll> dist(n + 1, INF);

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        ll p;
        cin >> a >> b >> c >> p;
        adjacency[a][c].push_back({p, {b, c}});
        adjacency[b][c].push_back({p, {a, c}});
        sumOfColour[a][c] += p;
        sumOfColour[b][c] += p;
    }

    priority_queue<pair<ll, pair<int, int>>> pq;
    dist[1] = 0;
    pq.push({0, {1, 0}});

    while (!pq.empty()) {
        auto [curCost, curAndColour] = pq.top();
        pq.pop();
        auto [cur, colour] = curAndColour;

        if (colour) {
            if (dp[cur][colour] != -curCost) continue;
            for (auto &edge : adjacency[cur][colour]) {
                ll curCase = sumOfColour[cur][colour] - edge.first - curCost;
                if (curCase < dist[edge.second.first]) {
                    dist[edge.second.first] = curCase;
                    pq.push({-curCase, {edge.second.first, 0}});
                }
            }
        } else if (-curCost == dist[cur]) {
            for (auto &c : adjacency[cur]) {
                for (auto &edge : c.second) {
                    ll curCase = sumOfColour[cur][edge.second.second] -
                                 edge.first - curCost;
                    if (curCase < dist[edge.second.first]) {
                        dist[edge.second.first] = curCase;
                        pq.push({-curCase, {edge.second.first, 0}});
                    }

                    curCase = edge.first - curCost;
                    if (curCase < dist[edge.second.first]) {
                        dist[edge.second.first] = curCase;
                        pq.push({-curCase, {edge.second.first, 0}});
                    }

                    curCase = -curCost;
                    if (!dp[edge.second.first].count(edge.second.second) ||
                        curCase < dp[edge.second.first][edge.second.second]) {
                        dp[edge.second.first][edge.second.second] = curCase;
                        pq.push({-curCase,
                                 {edge.second.first, edge.second.second}});
                    }
                }
            }
        }
    }

    cout << (dist[n] == INF ? -1 : dist[n]) << endl;

    return 0;
}

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