제출 #770586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
770586		Blagoj	Robot (JOI21_ho_t4)	C++17	34 / 100	3130 ms	2040104 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()

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

void solve() {
    priority_queue<tuple<ll, int, int>> pq;
    pq.push({0, 1, 0});
    while (pq.size() > 0) {
        ll dist;
        int place, color;
        tie(dist, place, color) = pq.top();
        dist *= -1;
        pq.pop();
        if (color) {
            if (dist != dp2[place][color]) continue;
            for (auto edge : edg[place][color]) {
                ll newCost = dist + sum[place][color] - get<2>(edge);
                if (newCost < dp[get<0>(edge)]) {
                    dp[get<0>(edge)] = newCost;
                    pq.push({-dp[get<0>(edge)], get<0>(edge), 0});
                }
            }
        }
        else {
            if (dist != dp[place]) continue;
            for (int i = 0; i < edg[place].size(); i++) {
                for (auto edge : edg[place][i]) {
                    ll newCost = dist + min((ll) get<2>(edge), sum[place][get<1>(edge)] - (ll) get<2>(edge));
                    if (newCost < dp[get<0>(edge)]) {
                        dp[get<0>(edge)] = newCost;
                        pq.push({-dp[get<0>(edge)], get<0>(edge), 0});
                    }
                    if (!dp2[get<0>(edge)].count(get<1>(edge)) || dist < dp2[get<0>(edge)][get<1>(edge)]) {
                        dp2[get<0>(edge)][get<1>(edge)] = dist;
                        pq.push({-dp2[get<0>(edge)][get<1>(edge)], get<0>(edge), get<1>(edge)});
                    }
                }
            }
        }
    }
    cout << ((dp[n] == 1e18) ? -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] = 1e18;
    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();
}

컴파일 시 표준 에러 (stderr) 메시지

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

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