Submission #517051

# Submission time Handle Problem Language Result Execution time Memory
517051 2022-01-22T12:50:54 Z nighty Commuter Pass (JOI18_commuter_pass) C++14
24 / 100
2000 ms 17008 KB
#include <bits/stdc++.h>

using namespace std;

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());
    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;
                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});
    }

    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:14:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |         for (auto [j, w] : g[i]) {
      |                   ^
# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 17008 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2005 ms 16344 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 57 ms 1404 KB Output is correct
2 Correct 22 ms 320 KB Output is correct
3 Correct 23 ms 332 KB Output is correct
4 Correct 96 ms 2280 KB Output is correct
5 Correct 68 ms 1344 KB Output is correct
6 Correct 35 ms 392 KB Output is correct
7 Correct 40 ms 332 KB Output is correct
8 Correct 61 ms 448 KB Output is correct
9 Correct 37 ms 328 KB Output is correct
10 Correct 67 ms 1488 KB Output is correct
11 Correct 7 ms 348 KB Output is correct
12 Correct 14 ms 352 KB Output is correct
13 Correct 22 ms 332 KB Output is correct
14 Correct 30 ms 380 KB Output is correct
15 Correct 32 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 17008 KB Time limit exceeded
2 Halted 0 ms 0 KB -