oj.uz

Submission #388325

# Submission time Handle Problem Language Result Execution time Memory
388325 2021-04-10T22:49:45 Z Kepha Robot (JOI21_ho_t4) C++11
100 / 100
 1141 ms 79920 KB 
// JOI 2021 Robot
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define MX 100000
using namespace std;

struct Edge {
    int color, next;
    ll price;

    Edge (int _color = 0, int _next = 0, ll _price = 0) {
        color = _color, next = _next, price = _price;
    }
};

struct Node {
    ll dist;
    int color, cur;

    Node (ll _dist = 0, int _color = 0, int _cur = 0) {
        dist = _dist, color = _color, cur = _cur;
    }

    bool operator<(const Node& x) const { return dist > x.dist; }
};

int N, M;
map<int, vector<Edge> > adj[MX + 1];
map<int, ll> sum[MX + 1], dist2[MX + 1];
ll dist1[MX + 1];
priority_queue<Node> q;

int main() {
    // ifstream cin("tmp");

    cin >> N >> M;

    for (int i = 1; i <= M; i++) {
        int a, b, c;
        ll d; 
        cin >> a >> b >> c >> d;

        adj[a][c].push_back(Edge(c, b, d));
        adj[b][c].push_back(Edge(c, a, d));   
        sum[a][c] += d;
        sum[b][c] += d;
    }

    fill(dist1 + 1, dist1 + 1 + N, INF);
    dist1[1] = 0;
    q.push(Node(0, 0, 1));

    while (q.size()) {
        int cur = q.top().cur, color = q.top().color;
        ll dist = q.top().dist;
        q.pop();
        
        if (color) {
            if (dist != dist2[cur][color]) continue;
            for (auto& edge : adj[cur][color]) {
                ll cost = sum[cur][color] - edge.price;
                if (cost + dist < dist1[edge.next]) {
                    dist1[edge.next] = cost + dist;
                    q.push(Node(cost + dist, 0, edge.next));
                }
            }
        }
        else {
            if (dist != dist1[cur]) continue;
            for (auto& c : adj[cur]) {
                for (auto& edge : c.second) {
                    ll cost1 = edge.price;
                    if (cost1 + dist < dist1[edge.next]) {
                        dist1[edge.next] = cost1 + dist;
                        q.push(Node(dist1[edge.next], 0, edge.next));
                    }

                    ll cost2 = sum[cur][edge.color] - edge.price;
                    if (cost2 + dist < dist1[edge.next]) {
                        dist1[edge.next] = cost2 + dist;
                        q.push(Node(dist1[edge.next], 0, edge.next));
                    }

                    if (dist2[edge.next].count(edge.color) == 0
                        || dist < dist2[edge.next][edge.color]) {

                        dist2[edge.next][edge.color] = dist;
                        
                        q.push(Node(dist2[edge.next][edge.color], edge.color, edge.next));
                    }
                }
            }
        }
    }

    if (dist1[N] >= INF) cout << "-1\n";
    else cout << dist1[N] << "\n";

    return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14284 KB Output is correct
2 Correct 8 ms 14284 KB Output is correct
3 Correct 8 ms 14284 KB Output is correct
4 Correct 8 ms 14284 KB Output is correct
5 Correct 9 ms 14444 KB Output is correct
6 Correct 8 ms 14284 KB Output is correct
7 Correct 10 ms 14540 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 13 ms 14924 KB Output is correct
10 Correct 12 ms 14924 KB Output is correct
11 Correct 11 ms 14668 KB Output is correct
12 Correct 10 ms 14696 KB Output is correct
13 Correct 11 ms 14668 KB Output is correct
14 Correct 11 ms 14744 KB Output is correct
15 Correct 10 ms 14540 KB Output is correct
16 Correct 12 ms 14640 KB Output is correct
17 Correct 11 ms 14668 KB Output is correct
18 Correct 10 ms 14540 KB Output is correct
19 Correct 14 ms 14540 KB Output is correct
20 Correct 11 ms 14668 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 32800 KB Output is correct
2 Correct 105 ms 23912 KB Output is correct
3 Correct 333 ms 28984 KB Output is correct
4 Correct 161 ms 26696 KB Output is correct
5 Correct 1111 ms 79648 KB Output is correct
6 Correct 930 ms 67912 KB Output is correct
7 Correct 509 ms 47948 KB Output is correct
8 Correct 600 ms 46796 KB Output is correct
9 Correct 634 ms 46884 KB Output is correct
10 Correct 438 ms 45364 KB Output is correct
11 Correct 211 ms 30788 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14284 KB Output is correct
2 Correct 8 ms 14284 KB Output is correct
3 Correct 8 ms 14284 KB Output is correct
4 Correct 8 ms 14284 KB Output is correct
5 Correct 9 ms 14444 KB Output is correct
6 Correct 8 ms 14284 KB Output is correct
7 Correct 10 ms 14540 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 13 ms 14924 KB Output is correct
10 Correct 12 ms 14924 KB Output is correct
11 Correct 11 ms 14668 KB Output is correct
12 Correct 10 ms 14696 KB Output is correct
13 Correct 11 ms 14668 KB Output is correct
14 Correct 11 ms 14744 KB Output is correct
15 Correct 10 ms 14540 KB Output is correct
16 Correct 12 ms 14640 KB Output is correct
17 Correct 11 ms 14668 KB Output is correct
18 Correct 10 ms 14540 KB Output is correct
19 Correct 14 ms 14540 KB Output is correct
20 Correct 11 ms 14668 KB Output is correct
21 Correct 270 ms 32800 KB Output is correct
22 Correct 105 ms 23912 KB Output is correct
23 Correct 333 ms 28984 KB Output is correct
24 Correct 161 ms 26696 KB Output is correct
25 Correct 1111 ms 79648 KB Output is correct
26 Correct 930 ms 67912 KB Output is correct
27 Correct 509 ms 47948 KB Output is correct
28 Correct 600 ms 46796 KB Output is correct
29 Correct 634 ms 46884 KB Output is correct
30 Correct 438 ms 45364 KB Output is correct
31 Correct 211 ms 30788 KB Output is correct
32 Correct 264 ms 24772 KB Output is correct
33 Correct 273 ms 26304 KB Output is correct
34 Correct 568 ms 46400 KB Output is correct
35 Correct 440 ms 38128 KB Output is correct
36 Correct 454 ms 43620 KB Output is correct
37 Correct 482 ms 45456 KB Output is correct
38 Correct 482 ms 52012 KB Output is correct
39 Correct 312 ms 27076 KB Output is correct
40 Correct 641 ms 46892 KB Output is correct
41 Correct 672 ms 46916 KB Output is correct
42 Correct 735 ms 55964 KB Output is correct
43 Correct 335 ms 34420 KB Output is correct
44 Correct 683 ms 37804 KB Output is correct
45 Correct 472 ms 43584 KB Output is correct
46 Correct 420 ms 44268 KB Output is correct
47 Correct 465 ms 44876 KB Output is correct
48 Correct 1141 ms 79920 KB Output is correct