제출 #1182351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182351		anteknne	Robot (JOI21_ho_t4)	C++20	100 / 100	142 ms	21552 KiB

Main

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

struct kraw {
    int a;
    int v;
    int c;
    ll p;
};

const int MAXN = 100 * 1000 + 1;
const int MAXM = 200 * 1000 + 1;
bool odw[MAXN];
vector<kraw> graf[MAXN];
priority_queue<pli> pq;
ll odl[MAXN];
ll suma[MAXM];
ll minn[MAXM];

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

    int n, m, a, b;
    cin >> n >> m;

    kraw x;
    for (int i = 0; i < m; i ++) {
        cin >> x.a >> x.v >> x.c >> x.p;
        graf[x.a].pb(x);
        swap(x.a, x.v);
        graf[x.a].pb(x);
    }

    for (int i = 1; i <= n; i ++) {
        odl[i] = LLONG_MAX/ll(1000);
    }

    pq.push({0, 1});
    odl[1] = 0;

    while (!pq.empty()) {
        ll aktodl = -pq.top().st;
        int v = pq.top().nd;

        pq.pop();

        if (odw[v]) {
            continue;
        }
        odw[v] = true;

        for (auto x : graf[v]) {
            suma[x.c] = 0LL;
            minn[x.c] = LLONG_MAX/ll(1000);
        }

        for (auto x : graf[v]) {
            suma[x.c] += x.p;
        }

        for (auto x : graf[v]) {
            minn[x.c] = min(minn[x.c], odl[x.v] + suma[x.c]);
        }

        for (auto u : graf[v]) {
                  //    zmien kolor     zmien wszystkie tego koloru oprocz tej
            ll x = min({odl[v] + u.p, odl[v] + suma[u.c] - u.p, minn[u.c] - u.p});
            if (x < odl[u.v]) {
                odl[u.v] = x;
                pq.push({-x, u.v});
            }
        }
    }

    if (odl[n] >= LLONG_MAX/ll(1000)) {
        cout << -1 << "\n";
        return 0;
    }

    cout << odl[n] << "\n";




    return 0;
}

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