Submission #870187

#	Time	Username	Problem	Language	Result	Execution time	Memory
870187		Pannda	Robot (JOI21_ho_t4)	C++14	34 / 100	3025 ms	126600 KiB

Main

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

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

    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edges(2 * m);
    vector<vector<int>> adj(n);
    vector<map<int, vector<int>>> alt_adj(n);
    vector<map<int, long long>> sum(n);

    for (int i = 0; i < m; i++) {
        int u, v, color, cost;
        cin >> u >> v >> color >> cost;
        u--;
        v--;

        edges[2 * i] = { v, color, cost };
        adj[u].push_back(2 * i);
        alt_adj[u][color].push_back(2 * i);
        sum[u][color] += cost;

        edges[2 * i + 1] = { u, color, cost };
        adj[v].push_back(2 * i + 1);
        alt_adj[v][color].push_back(2 * i + 1);
        sum[v][color] += cost;
    }

    map<array<int, 3>, long long> dist; // (u, e, changed) -> distance
    vector<bool> first_time(n, true);
    vector<long long> ans(n, -1);
    priority_queue<pair<long long, array<int, 3>>, vector<pair<long long, array<int, 3>>>, greater<>> pq;
    dist[{0, -1, 0}] = 0;
    pq.push({0, {0, -1, 0}});

    while (!pq.empty()) {
        auto [d, arr] = pq.top();
        auto [u, e, changed] = arr;
        pq.pop();

        if (dist[arr] != d) continue;

        if (first_time[u]) {
            ans[u] = d;
            for (int i : adj[u]) {
                auto [v, color, cost] = edges[i];
                if (!dist.count({v, i, 0}) || dist[{v, i, 0}] > d + sum[u][color] - cost) {
                    dist[{v, i, 0}] = d + sum[u][color] - cost;
                    pq.push({d + sum[u][color] - cost, {v, i, 0}});
                }
                if (!dist.count({v, i, 1}) || dist[{v, i, 1}] > d + cost) {
                    dist[{v, i, 1}] = d + cost;
                    pq.push({d + cost, {v, i, 1}});
                }
            }
            first_time[u] = false;
        }

        if (changed) {
            assert(e >= 0);
            auto [_u, color0, cost0] = edges[e];
            for (int i : alt_adj[u][color0]) {
                if ((i ^ 1) == e) continue;
                auto [v, color, cost] = edges[i];
                if (!dist.count({v, i, 0}) || dist[{v, i, 0}] > d + sum[u][color] - cost0 - cost) {
                    dist[{v, i, 0}] = d + sum[u][color] - cost0 - cost;
                    pq.push({d + sum[u][color] - cost0 - cost, {v, i, 0}});
                }
            }
        }
    }

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

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         auto [d, arr] = pq.top();
      |              ^
Main.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         auto [u, e, changed] = arr;
      |              ^
Main.cpp:49:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |                 auto [v, color, cost] = edges[i];
      |                      ^
Main.cpp:64:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |             auto [_u, color0, cost0] = edges[e];
      |                  ^
Main.cpp:67:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |                 auto [v, color, cost] = edges[i];
      |                      ^

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