Submission #770562

#	Time	Username	Problem	Language	Result	Execution time	Memory
770562		Blagoj	Robot (JOI21_ho_t4)	C++17	34 / 100	3023 ms	2097152 KiB

Main

#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

struct Node {
    int to, color, cost;
};

map<int, vector<Node>> edg[100005];
unordered_map<int, ll> sum[100005], dp2[100005];
ll dp[100005];
int n, m;

struct T {
    ll dist;
    int place, color;
};

bool operator < (T a, T b) { return a.dist > b.dist; }

void solve() {
    priority_queue<T> pq;
    pq.push({0, 1, 0});
    while (pq.size() > 0) {
        T top = pq.top();
        pq.pop();
        if (top.color) {
            if (top.dist != dp2[top.place][top.color]) continue;
            for (auto [to, color, cost] : edg[top.place][top.color]) {
                ll newCost = top.dist + sum[top.place][color] - cost;
                if (newCost < dp[to]) {
                    dp[to] = newCost;
                    pq.push({dp[to], to, 0});
                }
            }
            continue;
        }
        if (top.dist != dp[top.place]) continue;
        for (int i = 0; i < edg[top.place].size(); i++) {
            for (auto [to, color, cost] : edg[top.place][i]) {
                ll newCost = top.dist + min((ll) cost, sum[top.place][color] - (ll) cost);
                if (newCost < dp[to]) {
                    dp[to] = newCost;
                    pq.push({dp[to], to, 0});
                }
                if (!dp2[to].count(color) || top.dist < dp2[to][color]) {
                    dp2[to][color] = top.dist;
                    pq.push({dp2[to][color], to, color});
                }
            }
        }
    }
    cout << ((dp[n] == LLONG_MAX) ? -1 : dp[n]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 2; i <= n; i++) dp[i] = LLONG_MAX;
    for (int i = 0; i < m; i++) {
        int from, to, color, cost;
        cin >> from >> to >> color >> cost;
        edg[from][color].push_back({to, color, cost});
        edg[to][color].push_back({from, color, cost});
        sum[from][color] += cost;
        sum[to][color] += cost;
    }
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<Node> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i < edg[top.place].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~

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