oj.uz

Submission #924526

# Submission time Handle Problem Language Result Execution time Memory
924526 2024-02-09T07:21:33 Z crafticat Robot (JOI21_ho_t4) C++17
0 / 100
 199 ms 22752 KB 
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int,int>;
constexpr int inf = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m;

    vector<vector<tuple<int,int,int>>> f(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        f[a].emplace_back(c,b,d);
        f[b].emplace_back(c,a,d);
    }

    vector<vector<pii>> g(n + 1);
    for (int i = 1; i <= n; ++i) {
        map<int, int> app;
        for (auto [c, node, d] : f[i]) {
            app[c]++;
        }

        for (auto [c, node, d] : f[i]) {
            if (app[c] == 1) g[i].emplace_back(node,0);
            else g[i].emplace_back(node,d);
        }
    }

    priority_queue<pii,vector<pii>,greater<>> pq;
    pq.emplace(0,1);

    vector<int> d(n + 1,inf);
    vector<bool> visited(n + 1);

    while (!pq.empty()) {
        auto [cost, cur] = pq.top();pq.pop();
        if (visited[cur]) continue;
        d[cur] = cost;
        visited[cur] = true;

        for (auto [child, len] : g[cur]) {
            if (visited[child]) continue;
            pq.emplace(len + cost,child);
        }
    }

    cout << d[n];
    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 8748 KB Output is correct
2 Correct 20 ms 4328 KB Output is correct
3 Correct 65 ms 13040 KB Output is correct
4 Correct 29 ms 6380 KB Output is correct
5 Incorrect 199 ms 22752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -