Submission #863761

#	Time	Username	Problem	Language	Result	Execution time	Memory
863761		phi	Robot (JOI21_ho_t4)	C++17	100 / 100	651 ms	63980 KiB

Main

#include <iostream>
#include <vector>
#include <array>
#include <utility>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<array<int, 3>>> adj(n);

    for (int i = 0; i < m; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        a--; b--;
        adj[a].push_back({ c, p, b });
        adj[b].push_back({ c, p, a });
    }

    vector<vector<long long>> dp(n);
    vector<vector<pair<int, long long>>> total(n);

    for (int i = 0; i < n; i++) {
        sort(adj[i].begin(), adj[i].end());
        for (int j = 0; j < adj[i].size(); j++) {
            if (j == 0 || total[i][total[i].size() - 1].first != adj[i][j][0])
                total[i].push_back({ adj[i][j][0], 0 });
            total[i][total[i].size() - 1].second += adj[i][j][1];
        }
        dp[i].resize(adj[i].size() + 1, 1e18);
    }

    priority_queue<pair<long long, array<int, 5>>> q;
    q.push({ 0, { 0, 0, 0, 0, 0 } });

    while (!q.empty()) {
        auto [ nd, x ] = q.top();
        // from v to u
        auto [ t, c, p, u, v ] = x;

        long long d = -nd;

        q.pop();

        if (dp[u][dp[u].size() - 1] > d) {
            dp[u][dp[u].size() - 1] = d;
            for (auto arr : adj[u]) {
                long long tot = (*lower_bound(total[u].begin(), total[u].end(), make_pair(arr[0], -1LL))).second;
                q.push({ -(d + tot - arr[1]), { 0, 0, 0, arr[2], u } });
                q.push({ -(d + arr[1]), { 1, arr[0], arr[1], arr[2], u } });
            }
        }

        if (t == 1) {
            auto st = lower_bound(adj[u].begin(), adj[u].end(), array<int, 3>{ c, p, v });
            int i = st - adj[u].begin();

            if (dp[u][i] <= d) continue;
            dp[u][i] = d;

            auto it = lower_bound(adj[u].begin(), adj[u].end(), array<int, 3>{ c + 1, -1, 0 });
            it--;

            if (it == st) {
                if (it == adj[u].begin()) continue;
                else it--;
            }

            if ((*it)[0] != c) continue;

            long long tot = (*lower_bound(total[u].begin(), total[u].end(), make_pair(c, -1LL))).second;
            auto [ c2, p2, v2 ] = *it;
            q.push({ -(d + tot - p - p2), { 0, 0, 0, v2, u } });
        }
    }

    long long ans = 1e18;
    for (auto e : dp[n - 1])
        ans = min(ans, e);

    if (ans == 1e18) cout << -1;
    else cout << ans;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int j = 0; j < adj[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

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