oj.uz

답안 #770590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
770590 2023-07-01T13:44:11 Z Blagoj Robot (JOI21_ho_t4) C++17
100 / 100
 787 ms 92924 KB 
#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[100005];
unordered_map<int, ll> sum[100005], dp2[100005];
ll dp[100005];
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 [to, color, cost] : edg[place][color]) {
                ll newCost = dist + sum[place][color] - cost;
                if (newCost < dp[to]) {
                    dp[to] = newCost;
                    pq.push({-dp[to], to, 0});
                }
            }
        }
        else {
            if (dist != dp[place]) continue;
            for (auto x : edg[place]) {
                for (auto [to, color, cost] : x.second) {
                    ll newCost = dist + min((ll) cost, sum[place][color] - (ll) cost);
                    if (newCost < dp[to]) {
                        dp[to] = newCost;
                        pq.push({-dp[to], to, 0});
                    }
                    if (!dp2[to].count(color) || dist < dp2[to][color]) {
                        dp2[to][color] = 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();
}

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 15984 KB Output is correct
4 Correct 9 ms 15956 KB Output is correct
5 Correct 9 ms 15972 KB Output is correct
6 Correct 8 ms 15988 KB Output is correct
7 Correct 9 ms 16084 KB Output is correct
8 Correct 9 ms 15956 KB Output is correct
9 Correct 11 ms 16636 KB Output is correct
10 Correct 10 ms 16596 KB Output is correct
11 Correct 9 ms 16376 KB Output is correct
12 Correct 11 ms 16420 KB Output is correct
13 Correct 10 ms 16468 KB Output is correct
14 Correct 10 ms 16468 KB Output is correct
15 Correct 9 ms 16288 KB Output is correct
16 Correct 10 ms 16468 KB Output is correct
17 Correct 10 ms 16380 KB Output is correct
18 Correct 9 ms 16128 KB Output is correct
19 Correct 10 ms 16212 KB Output is correct
20 Correct 9 ms 16340 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 36272 KB Output is correct
2 Correct 60 ms 26892 KB Output is correct
3 Correct 130 ms 32464 KB Output is correct
4 Correct 92 ms 31196 KB Output is correct
5 Correct 779 ms 91132 KB Output is correct
6 Correct 589 ms 81544 KB Output is correct
7 Correct 290 ms 66468 KB Output is correct
8 Correct 351 ms 64120 KB Output is correct
9 Correct 364 ms 64224 KB Output is correct
10 Correct 281 ms 51320 KB Output is correct
11 Correct 113 ms 38760 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 15984 KB Output is correct
4 Correct 9 ms 15956 KB Output is correct
5 Correct 9 ms 15972 KB Output is correct
6 Correct 8 ms 15988 KB Output is correct
7 Correct 9 ms 16084 KB Output is correct
8 Correct 9 ms 15956 KB Output is correct
9 Correct 11 ms 16636 KB Output is correct
10 Correct 10 ms 16596 KB Output is correct
11 Correct 9 ms 16376 KB Output is correct
12 Correct 11 ms 16420 KB Output is correct
13 Correct 10 ms 16468 KB Output is correct
14 Correct 10 ms 16468 KB Output is correct
15 Correct 9 ms 16288 KB Output is correct
16 Correct 10 ms 16468 KB Output is correct
17 Correct 10 ms 16380 KB Output is correct
18 Correct 9 ms 16128 KB Output is correct
19 Correct 10 ms 16212 KB Output is correct
20 Correct 9 ms 16340 KB Output is correct
21 Correct 146 ms 36272 KB Output is correct
22 Correct 60 ms 26892 KB Output is correct
23 Correct 130 ms 32464 KB Output is correct
24 Correct 92 ms 31196 KB Output is correct
25 Correct 779 ms 91132 KB Output is correct
26 Correct 589 ms 81544 KB Output is correct
27 Correct 290 ms 66468 KB Output is correct
28 Correct 351 ms 64120 KB Output is correct
29 Correct 364 ms 64224 KB Output is correct
30 Correct 281 ms 51320 KB Output is correct
31 Correct 113 ms 38760 KB Output is correct
32 Correct 102 ms 27792 KB Output is correct
33 Correct 111 ms 32116 KB Output is correct
34 Correct 345 ms 51764 KB Output is correct
35 Correct 265 ms 45388 KB Output is correct
36 Correct 285 ms 60436 KB Output is correct
37 Correct 366 ms 63028 KB Output is correct
38 Correct 304 ms 68648 KB Output is correct
39 Correct 107 ms 31744 KB Output is correct
40 Correct 362 ms 65496 KB Output is correct
41 Correct 373 ms 65648 KB Output is correct
42 Correct 459 ms 68892 KB Output is correct
43 Correct 152 ms 37060 KB Output is correct
44 Correct 260 ms 39316 KB Output is correct
45 Correct 306 ms 62380 KB Output is correct
46 Correct 263 ms 61628 KB Output is correct
47 Correct 296 ms 62824 KB Output is correct
48 Correct 787 ms 92924 KB Output is correct