oj.uz

Submission #489749

# Submission time Handle Problem Language Result Execution time Memory
489749 2021-11-24T08:05:18 Z AndrewZhang Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 400 ms 20152 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
#define pb push_back
#define f first
#define s second

const int INF = 2e9;
const int maxN = 1e5;

int N, M, S, T, U, V;
ll distS[maxN], distT[maxN], distU[maxN], distV[maxN], minU[maxN], minV[maxN];
int parent[maxN];
vector<pair<int, int>> adj[maxN];

void dijkstra(int s, ll (&dist)[maxN]) {
    for (int i = 0; i < N; i++) {
        dist[i] = LLONG_MAX;
    }
    dist[s] = 0;
    priority_queue<pair<ll, int>> q;
    q.push({0, s});
    while(!q.empty()) {
        ll cdist = -q.top().first;
        int node = q.top().second;
        q.pop();
        if (cdist != dist[node]) continue;
        for (pair<int, int> i : adj[node]) {
            if (cdist + i.second < dist[i.first]) {
                dist[i.first] = cdist + i.second;
                q.push({-dist[i.first], i.first});
            }
        }
    }
}

void dijkstra2(int s, ll (&dist)[maxN]) {
    for (int i = 0; i < N; i++) {
        dist[i] = LLONG_MAX;
    }
    dist[s] = 0;
    priority_queue<pair<ll, int>> q;
    q.push({0, s});
    minU[s] = distU[s];
    minV[s] = distV[s];

    while(!q.empty()) {
        ll cdist = -q.top().first;
        int node = q.top().second;
        q.pop();
        if (cdist != dist[node]) continue;
        for (pair<int, int> i : adj[node]) {
            if (cdist + i.second < dist[i.first]) {
                parent[i.first] = node;
                dist[i.first] = cdist + i.second;
                minU[i.first] = min(minU[node], distU[i.first]);
                minV[i.first] = min(minV[node], distV[i.first]);
                q.push({-dist[i.first], i.first});
            }
            else if (cdist + i.second == dist[i.first]) {
                if (minU[node] + minV[node] < minU[i.first] + minV[i.first]) {
                    parent[i.first] = node;
                    minU[i.first] = min(minU[node], distU[i.first]);
                    minV[i.first] = min(minV[node], distV[i.first]);
                }
            }
        }
    }
}

int main() {
    // freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
    // freopen("pump.in", "r", stdin);
	// freopen("pump.out", "w", stdout);

    cin >> N >> M >> S >> T >> U >> V;
    S--; T--; U--; V--;
    for (int i = 0; i < M; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a-1].pb({b-1, w});
        adj[b-1].pb({a-1, w});
    }

    dijkstra(U, distU);
    dijkstra(V, distV);

    dijkstra2(S, distS);
    vector<int> path;
    int curr = T;

    while (curr != S) {
        curr = parent[curr];
        path.pb(curr);
    }
    reverse(path.begin(), path.end());

    ll pathToU, pathToV;
    pathToU = pathToV = LLONG_MAX;
    for (int i : path) {
        pathToU = min(pathToU, distU[i]);
        pathToV = min(pathToV, distV[i]);
    }
    cout << min(pathToU + pathToV, distU[V]);
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 20152 KB Output is correct
2 Correct 400 ms 18672 KB Output is correct
3 Correct 337 ms 18560 KB Output is correct
4 Correct 328 ms 19120 KB Output is correct
5 Incorrect 343 ms 18308 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 18900 KB Output is correct
2 Incorrect 376 ms 18516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 20152 KB Output is correct
2 Correct 400 ms 18672 KB Output is correct
3 Correct 337 ms 18560 KB Output is correct
4 Correct 328 ms 19120 KB Output is correct
5 Incorrect 343 ms 18308 KB Output isn't correct
6 Halted 0 ms 0 KB -