Submission #1298835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298835		uranium235	Robot (JOI21_ho_t4)	C++17	100 / 100	674 ms	97408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <class a, class b> ostream& operator<<(ostream &l, const pair<a, b> &r) {
    l << "(" << r.first << ", " << r.second << ")";
    return l;
}

template <class t, unsigned long int s> ostream& operator<<(ostream &l, const array<t, s> &r) {
    l << "[";
    for (int i = 0; i + 1 < s; i++) l << r[i] << ", ";
    if (s > 0) l << r[s - 1];
    l << "]";
    return l;
}

template <class t> ostream& operator<<(ostream &l, const vector<t> &r) {
    l << "{";
    for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", ";
    if (!r.empty()) l << r.back();
    l << "}";
    return l;
}


struct token {
    int v, t, c;
    ll w;
};

bool operator>(const token &l, const token &r) {
    return l.w > r.w;
}

ostream& operator<<(ostream &l, const token &r) {
    l << r.v << " " << r.t << " " << r.c << " " << r.w;
    return l;
}

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

    int n, m;
    cin >> n >> m;
    vector<map<int, vector<pair<int, int>>>> adj(n);
    vector<map<int, ll>> tot(n);
    for (int i = 0; i < m; i++) {
        int a, b, c, w;
        cin >> a >> b >> c >> w;
        a--, b--;
        adj[a][c].push_back({b, w});
        adj[b][c].push_back({a, w});
        tot[a][c] += w;
        tot[b][c] += w;
    }

    vector<ll> dp(n, -1);
    vector<map<int, ll>> dp1(n);
    priority_queue<token, vector<token>, greater<token>> pq;
    pq.push({0, 0, 0, 0});

    while (!pq.empty()) {
        token x = pq.top();
        pq.pop();
        if (x.t) {
            if (dp1[x.v].find(x.c) != dp1[x.v].end()) continue;
            dp1[x.v][x.c] = x.w;
            ll total = tot[x.v][x.c];
            for (pair<int, int> &i : adj[x.v][x.c]) {
                pq.push({i.first, 0, x.c, x.w + total - i.second});
            }
        } else {
            if (dp[x.v] != -1) continue;
            dp[x.v] = x.w;
            
            for (auto& [k, v] : adj[x.v]) {
                for (pair<int, int> &i : v) {
                    ll val = min(ll(i.second), tot[x.v][k] - i.second);
                    pq.push({i.first, 0, -1, x.w + val});
                    pq.push({i.first, 1, k, x.w});
                }
            }
        }
    }

    cout << dp[n - 1] << '\n';
}

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