oj.uz

Submission #963074

# Submission time Handle Problem Language Result Execution time Memory
963074 2024-04-14T12:59:21 Z toast12 Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 343 ms 17956 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e15;

int n, m;
vector<vector<pair<int, int>>> adj;

void dijkstras(vector<int> &parent, vector<long long> &dist, int start) {
    priority_queue<pair<int, int>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int x = pq.top().second;
        pq.pop();
        for (auto e : adj[x]) {
            int w = e.second;
            if (w + dist[x] < dist[e.first]) {
                parent[e.first] = x;
                dist[e.first] = dist[x]+w;
                pq.push({-dist[e.first], e.first});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    adj.resize(n+1);
    int s, t, u, v;
    cin >> s >> t >> u >> v;
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    vector<int> p(n+1);
    p[s] = s;
    vector<long long> d(n+1, INF);
    d[s] = 0;
    dijkstras(p, d, s);
    vector<int> path;
    int x = t;
    while (x != s) {
        path.push_back(x);
        x = p[x];
    }
    path.push_back(s);
    vector<int> from_u(n+1);
    vector<long long> du(n+1, INF);
    du[u] = 0;
    dijkstras(from_u, du, u);
    vector<int> from_v(n+1);
    vector<long long> dv(n+1, INF);
    dv[v] = 0;
    dijkstras(from_v, dv, v);
    long long ans = du[v];
    long long mnu = INF, mnv = INF;
    for (int i = 0; i < path.size(); i++) {
        mnu = min(mnu, du[path[i]]);
        mnv = min(mnv, dv[path[i]]);
        ans = min(ans, mnu+mnv);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < path.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 17956 KB Output is correct
2 Correct 273 ms 16880 KB Output is correct
3 Correct 319 ms 17520 KB Output is correct
4 Incorrect 235 ms 17896 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 17100 KB Output is correct
2 Correct 247 ms 16932 KB Output is correct
3 Correct 277 ms 17188 KB Output is correct
4 Correct 271 ms 16964 KB Output is correct
5 Correct 232 ms 17152 KB Output is correct
6 Correct 251 ms 17256 KB Output is correct
7 Correct 250 ms 17264 KB Output is correct
8 Correct 295 ms 17080 KB Output is correct
9 Correct 275 ms 17236 KB Output is correct
10 Correct 292 ms 16932 KB Output is correct
11 Correct 109 ms 11776 KB Output is correct
12 Correct 251 ms 17456 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 17956 KB Output is correct
2 Correct 273 ms 16880 KB Output is correct
3 Correct 319 ms 17520 KB Output is correct
4 Incorrect 235 ms 17896 KB Output isn't correct
5 Halted 0 ms 0 KB -