oj.uz

Submission #963127

# Submission time Handle Problem Language Result Execution time Memory
963127 2024-04-14T14:40:12 Z toast12 Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 2000 ms 37068 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int n, m;
int s, t, u, v;
long long ans;
long long mnu = INF, mnv = INF;

vector<vector<pair<int, long long>>> adj;
vector<vector<int>> p;
vector<bool> visited;
vector<int> path;
vector<long long> dv, du;
vector<bool> done;
stack<int> prevu, prevv;

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

void find_path() {
    long long temp_ans = INF;
    if (path.back() == s)
        return;
    for (auto x : p[path.back()]) {
        path.push_back(x);
        mnu = min(mnu, du[x]);
        prevu.push(mnu);
        mnv = min(mnv, dv[x]);
        prevv.push(mnv);
        find_path();
        path.pop_back();
        temp_ans = min(temp_ans, mnu+mnv);
        prevu.pop();
        prevv.pop();
        mnv = prevv.top();
        mnu = prevu.top();
    }
    ans = min(ans, temp_ans);
}

int main() {
    cin >> n >> m;
    adj.resize(n+1);
    p.resize(n+1);
    visited.resize(n+1);
    cin >> s >> t >> u >> v;
    for (int i = 0; i < m; i++) {
        int x, y;
        long long w;
        cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    p[s].push_back(s);
    vector<long long> d(n+1, INF);
    d[s] = 0;
    dijkstras(p, d, s);
    vector<vector<int>> temp(n+1);
    dv.resize(n+1, INF);
    dv[v] = 0;
    fill(visited.begin(), visited.end(), false);
    dijkstras(temp, dv, v);
    du.resize(n+1, INF);
    du[u] = 0;
    fill(visited.begin(), visited.end(), false);
    dijkstras(temp, du, u);
    ans = du[v];
    path.push_back(t);
    prevu.push(du[t]);
    prevv.push(dv[t]);
    mnu = du[t], mnv = dv[t];
    find_path();
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 32412 KB Output is correct
2 Execution timed out 2025 ms 31148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 33588 KB Output is correct
2 Correct 350 ms 33816 KB Output is correct
3 Correct 337 ms 33108 KB Output is correct
4 Correct 367 ms 33548 KB Output is correct
5 Correct 396 ms 34368 KB Output is correct
6 Correct 400 ms 36184 KB Output is correct
7 Correct 393 ms 37068 KB Output is correct
8 Correct 406 ms 33648 KB Output is correct
9 Correct 371 ms 34384 KB Output is correct
10 Correct 347 ms 33220 KB Output is correct
11 Incorrect 164 ms 29732 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 2136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 32412 KB Output is correct
2 Execution timed out 2025 ms 31148 KB Time limit exceeded
3 Halted 0 ms 0 KB -