Submission #880663

#	Time	Username	Problem	Language	Result	Execution time	Memory
880663		MisterReaper	Robot (JOI21_ho_t4)	C++17	100 / 100	748 ms	82748 KiB

Main

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

const int MAXN = 1E5 + 5;
const i64 INF = 1E15;

i64 ncost;

i64 dp1[MAXN];
map <int, i64> sum[MAXN], dp2[MAXN];
map <int, vector <pair <int, int>>> adj[MAXN];

#define ONLINE_JUDGE
void solve() {
    fill(dp1, dp1 + MAXN, INF);

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

    for(int i = 1; i <= m; i++) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;

        adj[u][c].emplace_back(v, p);
        adj[v][c].emplace_back(u, p);
        sum[u][c] += p;
        sum[v][c] += p;
    }

    using T = tuple <i64, int, int>;
    priority_queue <T, vector <T>, greater <T>> pq; // [cost, ok, node]

    pq.emplace(dp1[1] = 0, -1, 1);
    while(!pq.empty()) {
        auto [cost, ok, node] = pq.top();
        pq.pop();

        if(ok == -1) {
            if(cost != dp1[node]) {
                continue;
            }

            for(auto &[color, vec] : adj[node]) {
                for(auto &[child, add] : vec) {
                    // Case 1: Flip neighbours
                    // Case 2: Flip yourself but don't your child's neighbours
                    ncost = cost + min(i64(add), sum[node][color] - add);
                    if(ncost < dp1[child]) {
                        //cerr << node << " " << cost << " -> " << child << " " << ncost << "\n";
                        pq.emplace(dp1[child] = ncost, -1, child);
                    }

                    // Case 3: Flip yourself and your child's neighbours
                    if(dp2[child].count(color) == 0 || cost < dp2[child][color]) {
                        //cerr << "go: " << node << " " << child << " :: " << color << " :: " << cost << "\n";
                        pq.emplace(dp2[child][color] = cost, color, child);
                    }
                }
            }
        } else {
            if(cost != dp2[node][ok]) {
                continue;
            }

            // Only Case 1: Flip neighbours (including before)
            for(auto &[child, add] : adj[node][ok]) {
                ncost = cost + (sum[node][ok] - add);
                if(ncost < dp1[child]) {
                    //cerr << "ex: " << node << " " << ok << " " << cost << " -> " << child << " " << ncost << "\n";
                    pq.emplace(dp1[child] = ncost, -1, child);
                }
            }
        }
    }

    cout << (dp1[n] == INF ? -1 : dp1[n]);
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

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