Submission #385035

#	Time	Username	Problem	Language	Result	Execution time	Memory
385035		timmyfeng	Robot (JOI21_ho_t4)	C++17	100 / 100	1058 ms	70576 KiB

Main

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

const int N = 100001;

map<int, vector<array<long long, 2>>> adj[N];
priority_queue<array<long long, 3>> que;
map<int, long long> dist[N];

void update(int c, int x, long long d) {
    if (dist[c].count(x) == 0 || d < dist[c][x]) {
        que.push({-d, c, x});
        dist[c][x] = d;
    }
}

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

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

    while (m--) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u][c].push_back({v, p});
        adj[v][c].push_back({u, p});
    }

    que.push({0, 1, 0});
    dist[1][0] = 0;

    while (!que.empty()) {
        auto [d, u, x] = que.top();
        que.pop();
        d = -d;

        if (d > dist[u][x]) {
            continue;
        }

        if (x == 0) {
            for (auto &[y, v] : adj[u]) {
                long long sum = 0;
                for (auto [c, w] : v) {
                    sum += w;
                }

                for (auto [c, w] : v) {
                    update(c, 0, d + min(w, sum - w));
                    update(c, y, d);
                }
            }
        } else {
            long long sum = 0;
            for (auto [c, w] : adj[u][x]) {
                sum += w;
            }

            for (auto [c, w] : adj[u][x]) {
                update(c, 0, d + sum - w);
            }
        }
    }

    cout << (dist[n].count(0) == 0 ? -1 : dist[n][0]) << "\n";
}

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