제출 #1133434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133434		hnay	Robot (JOI21_ho_t4)	C++20	100 / 100	1538 ms	186004 KiB

Main

#include <bits/stdc++.h>

#define pb push_back
#define st first
#define nd second

using ll = long long;
using ld = long double;

using namespace std;

struct edge {
    int to, c;
    ll p;
    edge(int to = 0, int c = 0, ll p = 0) : to(to), c(c), p(p) {}
};

const ll INF = 1e16;
const int MN = 100005;
int n, m;

map <int, vector <edge> > v[MN];
map <int, vector <edge> > vec[MN];

map <int, bool> visited[MN];
map <int, ll> p_sum[MN], dp[MN]; // suma kosztow p dla koloru c | minimalny koszt dotarcia do wierzchołka v krawędzią o kolorze c

// X: pokoloruj krawędź
// Y: pokoloruj wszystkie inne

priority_queue <pair<ll, pair <int, int> > > pq; // koszt, wierzchołek, kolor

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

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        v[a][0].pb(edge(b, c, p)); // Y: a -> b
        v[b][0].pb(edge(a, c, p)); // X: b -> a
        p_sum[a][c] += p;
        p_sum[b][c] += p;
    }
    for(int i = 1; i <= n; i++) {
        dp[i][0] = INF;
        vector <edge> ve = v[i][0];
        vec[i][0] = ve;
        for(int ii = 0; ii < (int)ve.size(); ii++) {
            dp[i][ve[ii].c] = INF;
            // from = i, to = ve[ii].to, colour = c, price = p
            vec[i][0].pb(edge(ve[ii].to, 0, ve[ii].p));  // v -> w (normalna)
            vec[i][0].pb(edge(ve[ii].to, ve[ii].c, 0));  // v -> e,c (koszt 0)
            vec[i][0].pb(edge(i, ve[ii].c, 0));  // v -> v,c (koszt 0)
            vec[ve[ii].to][0].pb(edge(ve[ii].to, ve[ii].c, 0)); // w -> e,c (koszt 0)
            vec[ve[ii].to][ve[ii].c].pb(edge(i, 0, p_sum[ve[ii].to][ve[ii].c] - ve[ii].p)); // e,c -> v (koszt sum_p - koszt_p_kr)
        }
    }
    dp[1][0] = 0;
    pq.push({0, {1, 0}});
    while(!pq.empty()) {
        pair <int, int> x = pq.top().nd; // wierzchołek kolor
        pq.pop();
        if(!visited[x.st][x.nd]) {
            visited[x.st][x.nd] = 1;
            ll koszt = dp[x.st][x.nd];
            // cout << x.st << ' ' << x.nd << " = " << koszt << "\n";
            vector <edge> ve = vec[x.st][x.nd];
            for(int i = 0; i < (int)ve.size(); i++) {
                if(!visited[ve[i].to][ve[i].c] && koszt + ve[i].p < dp[ve[i].to][ve[i].c]) {
                    dp[ve[i].to][ve[i].c] = koszt + ve[i].p;
                    pq.push({-(koszt + ve[i].p), {ve[i].to, ve[i].c}});
                }
            }
        }
    }

    // for(int i = 1; i <= n; i++) {
    //     cout << "---------- " << i << " -----------\n";
    //     for(int ii = 0; ii < vec[i][0].size(); ii++) {
    //         cout << i << " ---> " << vec[i][0][ii].to << " (" << vec[i][0][ii].c << ',' << vec[i][0][ii].p << ")\n";
    //     }
    // }

    if(dp[n][0] == INF) {
        cout << "-1";
    }
    else {
        cout << dp[n][0];
    }

    return 0;
}

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