oj.uz

Submission #963091

# Submission time Handle Problem Language Result Execution time Memory
963091 2024-04-14T13:53:38 Z toast12 Commuter Pass (JOI18_commuter_pass) C++14
16 / 100
 302 ms 30236 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int n, m;
int s, t, u, v;
vector<vector<pair<int, long long>>> adj;
vector<vector<int>> p;
vector<bool> visited;
vector<bool> on_path;
vector<bool> processed;

void dfs(int cur) {
    if (processed[cur])
        return;
    on_path[cur] = true;
    processed[cur] = true;
    for (auto x : p[cur]) {
        dfs(x);
    }
}

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

int main() {
    cin >> n >> m;
    adj.resize(n+1);
    p.resize(n+1);
    processed.resize(n+1);
    on_path.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);
    for (auto x : p[t]) {
        dfs(x);
    }
    on_path[t] = true;
    vector<vector<int>> temp(n+1);
    vector<long long> dv(n+1, INF);
    dv[v] = 0;
    fill(visited.begin(), visited.end(), false);
    dijkstras(temp, dv, v);
    long long ans = INF;
    long long mnv = INF;
    for (int i = 1; i <= n; i++) {
        if (!on_path[i])
            continue;
        mnv = min(mnv, dv[i]);
        ans = min(ans, mnv);
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 26580 KB Output is correct
2 Correct 287 ms 25988 KB Output is correct
3 Correct 262 ms 27552 KB Output is correct
4 Correct 281 ms 26408 KB Output is correct
5 Correct 301 ms 29184 KB Output is correct
6 Correct 294 ms 30224 KB Output is correct
7 Correct 279 ms 29328 KB Output is correct
8 Correct 291 ms 29168 KB Output is correct
9 Correct 291 ms 30104 KB Output is correct
10 Correct 254 ms 29948 KB Output is correct
11 Correct 123 ms 23444 KB Output is correct
12 Correct 297 ms 30236 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 26716 KB Output is correct
2 Correct 302 ms 27008 KB Output is correct
3 Incorrect 280 ms 26480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1624 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 26580 KB Output is correct
2 Correct 287 ms 25988 KB Output is correct
3 Correct 262 ms 27552 KB Output is correct
4 Correct 281 ms 26408 KB Output is correct
5 Correct 301 ms 29184 KB Output is correct
6 Correct 294 ms 30224 KB Output is correct
7 Correct 279 ms 29328 KB Output is correct
8 Correct 291 ms 29168 KB Output is correct
9 Correct 291 ms 30104 KB Output is correct
10 Correct 254 ms 29948 KB Output is correct
11 Correct 123 ms 23444 KB Output is correct
12 Correct 297 ms 30236 KB Output is correct
13 Correct 300 ms 26716 KB Output is correct
14 Correct 302 ms 27008 KB Output is correct
15 Incorrect 280 ms 26480 KB Output isn't correct
16 Halted 0 ms 0 KB -