Submission #1159637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159637		bbldrizzy	Robot (JOI21_ho_t4)	C++20	0 / 100	420 ms	70652 KiB

Main

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
vector<map<ll, ll>> adj;
vector<ll> dp1;
vector<map<ll, ll>> dp2;


int main() {
	ll n,m; cin >> n >> m;
    adj.resize(n+1);
    vector<vector<pair<int, P>>> ajd(n+1);
    dp1.resize(n+1, 1e9);
    dp2.resize(n+1);
    for (int i = 0; i < m; i++) {
        ll a, b, c, p; cin >> a >> b >> c >> p;
        adj[a][c] += p;
        adj[b][c] += p;
        ajd[a].push_back({b, {c, p}}); // leading node, color, cost: <node, <color, cost>>
        ajd[b].push_back({a, {c, p}});
    }   
    vector<vector<pair<int, P>>> AJD = ajd;
    /*
    for (int i = 1; i <= n; i++) {
        for (auto u1: ajd[i]) {
            cout << "u: " << u1.f << ", " << u1.s.f << ", " << u1.s.s << "\n";
        }
        cout << "\n";
    }
    cout << "\n";
    cout << "\n";
    cout << "\n";
    cout << "\n";
    */
    for (int i = 1; i <= n; i++) {
        for (auto &u: ajd[i]) {
            //if (u.s.s != adj[i][u.s.f]) u.s.s = min(adj[i][u.s.f]-u.s.s, u.s.s);
            u.s.s = min(adj[i][u.s.f]-u.s.s, u.s.s);
        }
    }
    /*
    for (int i = 1; i <= n; i++) {
        for (auto u1: ajd[i]) {
            cout << "u: " << u1.f << ", " << u1.s.f << ", " << u1.s.s << "\n";
        }
        cout << "\n";
    }
    */
    
    priority_queue<P, vector<P>, greater<P>> pq;
    ll start = 1;
    dp1[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        P u = pq.top(); pq.pop();
        if (u.f != dp1[u.s]) continue;
        //cout << "u(val, node): " << u.f << ", " << u.s << "\n";
        ll counter = 0;
        for (pair<int, P> u1: ajd[u.s]) {
            //cout << "u1(nxtnode, color, cost): " << u1.f << ", " << u1.s.f << ", " << u1.s.s << '\n';
            if (dp2[u1.f].count(u1.s.f) > 0) {
                //cout << "dp2 of u1.f, u1.s.f MAY BECOME dp1 of u.s: " << u1.f << ", " << u1.s.f << " ::: " << u.s << "\n";
                //cout << "dp2[u1.f][u1.s.f], dp1[u.s]: " << dp2[u1.f][u1.s.f] << ", " << dp1[u.s] << '\n';
                dp2[u1.f][u1.s.f] = min(dp2[u1.f][u1.s.f], dp1[u.s]);
            } else {
                //cout << "dp2 of u1.f, u1.s.f becomes dp1 of u.s: " << u1.f << ", " << u1.s.f << " ::: " << u.s << "\n";
                //cout << "dp1[u.s]: " << dp1[u.s] << '\n';
                dp2[u1.f][u1.s.f] = dp1[u.s];
            }
            if (u1.s.s != AJD[u.s][counter].s.s) {
                ll v1 = dp1[u.s]+u1.s.s;
                bool truzz = dp2[u.s].count(u1.s.f)>0;
                if (truzz) {
                    ll v2 = dp2[u.s][u1.s.f]+u1.s.s;
                    if (v1 < dp1[u1.f] || v2 < dp1[u1.f]) {
                        //cout << "u, dp1[u.s], u1.s.s: " << u.s << ", " << dp1[u.s] << "\n";
                        //cout << "yo wtf here are u1.f, v1, v2: " << u1.f << ", " << v1 << ", " << v2 << "\n";
                        pq.push({dp1[u1.f]=min(v1, v2), u1.f});
                    }
                } else {
                    if (v1 < dp1[u1.f]) {
                        pq.push({dp1[u1.f]=v1, u1.f});
                    }
                }
            } else {
                if (dp1[u.s] + u1.s.s < dp1[u1.f]) {
                    //cout << "YO, u1.f, u.s, dp1[u.s], u1.s.s: " << u1.f << ", " << u.s << ", " << dp1[u.s] << ", " << u1.s.s << '\n';
                    dp1[u1.f] = dp1[u.s]+u1.s.s;
                    pq.push({dp1[u1.f], u1.f});
                }
            }
            counter++;
        }
    }
    
    if (dp1[n] != 1e9) {
        cout << dp1[n];
    } else {
        cout << -1;
    }
}

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