oj.uz

Submission #388313

# Submission time Handle Problem Language Result Execution time Memory
388313 2021-04-10T22:18:25 Z Kepha Robot (JOI21_ho_t4) C++11
24 / 100
 1135 ms 76236 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<pair<int, int> > > 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, d; cin >> a >> b >> c >> d;
        adj[a][c].push_back({b, d});
        adj[b][c].push_back({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, 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.second;
                if (cost + dist < dist1[edge.first]) {
                    dist1[edge.first] = cost + dist;
                    q.push(node(cost + dist, 0, edge.first));
                }
            }
        }
        else {
            if (dist != dist1[cur]) continue;
            for (auto& c : adj[cur]) {
                for (auto& edge : c.second) {
                    ll cost1 = edge.second;
                    if (cost1 + dist < dist1[edge.first]) {
                        dist1[edge.first] = cost1 + dist;
                        q.push(node(cost1 + dist, 0, edge.first));
                    }

                    ll cost2 = sum[cur][c.first] - edge.second;
                    if (cost2 + dist < dist1[edge.first]) {
                        dist1[edge.first] = cost2 + dist;
                        q.push(node(cost2 + dist, 0, edge.first));
                    }

                    if (dist2[edge.first].count(c.first) == 0 
                        || dist < dist2[edge.first][c.first]) {
                        dist2[edge.first][c.first] = dist;
                        q.push(node(dist, c.first, edge.first));
                    }
                }
            }
        }
    }

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

    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14392 KB Output is correct
2 Correct 8 ms 14284 KB Output is correct
3 Correct 7 ms 14284 KB Output is correct
4 Correct 9 ms 14296 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14284 KB Output is correct
7 Correct 9 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 14796 KB Output is correct
11 Correct 11 ms 14648 KB Output is correct
12 Correct 10 ms 14620 KB Output is correct
13 Correct 11 ms 14668 KB Output is correct
14 Correct 11 ms 14668 KB Output is correct
15 Incorrect 10 ms 14580 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 31340 KB Output is correct
2 Correct 130 ms 23412 KB Output is correct
3 Correct 311 ms 26176 KB Output is correct
4 Correct 187 ms 25752 KB Output is correct
5 Correct 1135 ms 76236 KB Output is correct
6 Correct 926 ms 64176 KB Output is correct
7 Correct 483 ms 43316 KB Output is correct
8 Correct 530 ms 42460 KB Output is correct
9 Correct 594 ms 42364 KB Output is correct
10 Correct 444 ms 43588 KB Output is correct
11 Correct 214 ms 29048 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14392 KB Output is correct
2 Correct 8 ms 14284 KB Output is correct
3 Correct 7 ms 14284 KB Output is correct
4 Correct 9 ms 14296 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 8 ms 14284 KB Output is correct
7 Correct 9 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 14796 KB Output is correct
11 Correct 11 ms 14648 KB Output is correct
12 Correct 10 ms 14620 KB Output is correct
13 Correct 11 ms 14668 KB Output is correct
14 Correct 11 ms 14668 KB Output is correct
15 Incorrect 10 ms 14580 KB Output isn't correct
16 Halted 0 ms 0 KB -