oj.uz

Submission #963106

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

const long long INF = 1e18;

int n, m;
int s, t, u, v;
long long ans;

vector<vector<pair<int, long long>>> adj;
vector<vector<int>> p;
vector<bool> visited;
vector<bool> processed;
vector<int> path;
vector<long long> dv, du;

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 evaluate() {
    long long mnu = INF, mnv = INF;
    for (auto node : path) {
        mnu = min(mnu, du[node]);
        mnv = min(mnv, dv[node]);
        ans = min(ans, mnu+mnv);
    }
}

void find_path() {
    if (path.back() == s) {
        evaluate();
        return;
    }
    for (auto x : p[path.back()]) {
        path.push_back(x);
        find_path();
        path.pop_back();
    }
}

int main() {
    cin >> n >> m;
    adj.resize(n+1);
    p.resize(n+1);
    processed.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];
    long long mnv = INF, mnu = INF;
    path.push_back(t);
    find_path();
    cout << ans << '\n';
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:90:15: warning: unused variable 'mnv' [-Wunused-variable]
   90 |     long long mnv = INF, mnu = INF;
      |               ^~~
commuter_pass.cpp:90:26: warning: unused variable 'mnu' [-Wunused-variable]
   90 |     long long mnv = INF, mnu = INF;
      |                          ^~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 29228 KB Output is correct
2 Execution timed out 2023 ms 27912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 28888 KB Output is correct
2 Correct 340 ms 29064 KB Output is correct
3 Correct 373 ms 28996 KB Output is correct
4 Correct 325 ms 29040 KB Output is correct
5 Correct 354 ms 29272 KB Output is correct
6 Correct 305 ms 30040 KB Output is correct
7 Correct 332 ms 30652 KB Output is correct
8 Correct 331 ms 29140 KB Output is correct
9 Correct 305 ms 29304 KB Output is correct
10 Correct 331 ms 29036 KB Output is correct
11 Correct 131 ms 24288 KB Output is correct
12 Correct 314 ms 30288 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 29228 KB Output is correct
2 Execution timed out 2023 ms 27912 KB Time limit exceeded
3 Halted 0 ms 0 KB -