Submission #517010

# Submission time Handle Problem Language Result Execution time Memory
517010 2022-01-22T11:10:20 Z nighty Commuter Pass (JOI18_commuter_pass) C++14
40 / 100
2000 ms 15872 KB
#include <bits/stdc++.h>

using namespace std;

vector<int> last;

set<pair<int, int>> choosenE;

vector<long long> dijkstra(int start, vector<vector<pair<int, int>>>& g) {
    int n = g.size();
    vector<long long> d(n, numeric_limits<long long>::max());
    last.assign(n, -1);
    d[start] = 0;
    set<pair<long long, int>> s; // {d[i], i}
    s.insert({0, start});
    while (!s.empty()) {
        int i = s.begin()->second;
        s.erase(s.begin());
        for (auto [j, w] : g[i]) {
            if (d[i] + w < d[j]) {
                s.erase({d[j], j});
                d[j] = d[i] + w;
                last[j] = i;
                s.insert({d[j], j});
            }
        }
    }
    return d;
}

vector<long long> dijkstra2(int start, vector<vector<pair<int, int>>>& g) {
    int n = g.size();
    vector<long long> d(n, numeric_limits<long long>::max());
    last.assign(n, -1);
    d[start] = 0;
    set<pair<long long, int>> s; // {d[i], i}
    s.insert({0, start});
    while (!s.empty()) {
        int i = s.begin()->second;
        s.erase(s.begin());
        for (auto [j, w] : g[i]) {
            if (choosenE.find({i, j}) != choosenE.end() || choosenE.find({j, i}) != choosenE.end()) {
                w = 0;
            }
            if (d[i] + w < d[j]) {
                s.erase({d[j], j});
                d[j] = d[i] + w;
                last[j] = i;
                s.insert({d[j], j});
            }
        }
    }
    return d;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int s, t;
    cin >> s >> t;
    --s, --t;
    int u, v;
    cin >> u >> v;
    --u, --v;
    vector<vector<pair<int, int>>> g(n);
    for (int _m = 0; _m < m; ++_m) {
        int a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    if (s == u) {
        long long minDistST = dijkstra(s, g)[t];
        auto dT = dijkstra(t, g), dV = dijkstra(v, g), dS = dijkstra(s, g);
        long long res = numeric_limits<long long>::max();
        for (int i = 0; i < n; ++i) {
            if (dS[i] + dT[i] == minDistST) {
                res = min(res, dV[i]);
            }
        }
        cout << res << '\n';
        return 0;
    }

//    SUBTASK 2
//    dijkstra(s, g);
//    while (t >= 0) {
//        choosenE.insert({last[t], t});
//        t = last[t];
//    }
//    auto d = dijkstra2(u, g);
//    cout << d[v] << '\n';

    long long minDistST = dijkstra(s, g)[t];
    auto dT = dijkstra(t, g), dV = dijkstra(v, g), dS = dijkstra(s, g), dU = dijkstra(u, g);
    long long res = dU[v];
    for (int i = 0; i < n; ++i) {
        auto di = dijkstra(i, g);
        for (int j = 0; j < n; ++j) {
            if (min(dS[i] + dT[j], dS[j] + dT[i]) + di[j] == minDistST) {
                res = min(res, min(dU[i] + dV[j], dU[j] + dV[i]));
            }
        }
    }
    cout << res << '\n';
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int, std::vector<std::vector<std::pair<int, int> > >&)':
commuter_pass.cpp:19:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |         for (auto [j, w] : g[i]) {
      |                   ^
commuter_pass.cpp: In function 'std::vector<long long int> dijkstra2(int, std::vector<std::vector<std::pair<int, int> > >&)':
commuter_pass.cpp:41:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for (auto [j, w] : g[i]) {
      |                   ^
# Verdict Execution time Memory Grader output
1 Correct 434 ms 14700 KB Output is correct
2 Correct 372 ms 13720 KB Output is correct
3 Correct 344 ms 13408 KB Output is correct
4 Correct 393 ms 14700 KB Output is correct
5 Correct 349 ms 13620 KB Output is correct
6 Correct 470 ms 14804 KB Output is correct
7 Correct 333 ms 13504 KB Output is correct
8 Correct 397 ms 13852 KB Output is correct
9 Correct 360 ms 13716 KB Output is correct
10 Correct 277 ms 13976 KB Output is correct
11 Correct 92 ms 8488 KB Output is correct
12 Correct 384 ms 13512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 15872 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 47 ms 972 KB Output is correct
2 Correct 22 ms 356 KB Output is correct
3 Correct 23 ms 332 KB Output is correct
4 Correct 61 ms 2460 KB Output is correct
5 Correct 71 ms 1356 KB Output is correct
6 Correct 36 ms 360 KB Output is correct
7 Correct 41 ms 572 KB Output is correct
8 Correct 61 ms 376 KB Output is correct
9 Correct 37 ms 304 KB Output is correct
10 Correct 53 ms 1372 KB Output is correct
11 Correct 6 ms 332 KB Output is correct
12 Correct 13 ms 316 KB Output is correct
13 Correct 21 ms 332 KB Output is correct
14 Correct 31 ms 332 KB Output is correct
15 Correct 32 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 434 ms 14700 KB Output is correct
2 Correct 372 ms 13720 KB Output is correct
3 Correct 344 ms 13408 KB Output is correct
4 Correct 393 ms 14700 KB Output is correct
5 Correct 349 ms 13620 KB Output is correct
6 Correct 470 ms 14804 KB Output is correct
7 Correct 333 ms 13504 KB Output is correct
8 Correct 397 ms 13852 KB Output is correct
9 Correct 360 ms 13716 KB Output is correct
10 Correct 277 ms 13976 KB Output is correct
11 Correct 92 ms 8488 KB Output is correct
12 Correct 384 ms 13512 KB Output is correct
13 Execution timed out 2081 ms 15872 KB Time limit exceeded
14 Halted 0 ms 0 KB -