Submission #557386

#	Time	Username	Problem	Language	Result	Execution time	Memory
557386		alextodoran	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	414 ms	23384 KiB

commuter_pass

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

int N, M;
int S, T;
int U, V;

struct Edge {
    int to;
    int cost;
};
vector <Edge> adj[N_MAX + 2];

bool seen[N_MAX + 2];
void Dijkstra (int start, ll dist[]) {
    fill(dist + 1, dist + N + 1, LLONG_MAX);
    fill(seen + 1, seen + N + 1, false);
    priority_queue <pair <ll, int>> q;
    dist[start] = 0;
    q.push(make_pair(-dist[start], start));
    while (q.empty() == false) {
        ll d; int u; tie(d, u) = q.top();
        q.pop();
        if (seen[u] == true) {
            continue;
        }
        seen[u] = true;
        for (Edge e : adj[u]) {
            if (dist[u] + e.cost < dist[e.to]) {
                dist[e.to] = dist[u] + e.cost;
                q.push(make_pair(-dist[e.to], e.to));
            }
        }
    }
}

ll distS[N_MAX + 2];
ll distT[N_MAX + 2];
ll distU[N_MAX + 2];
ll distV[N_MAX + 2];

vector <int> out[N_MAX + 2];
int cntin[N_MAX + 2];

ll minU[N_MAX + 2];
ll minV[N_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    cin >> S >> T;
    cin >> U >> V;
    for (int i = 1; i <= M; i++) {
        int u, v, cost;
        cin >> u >> v >> cost;
        adj[u].push_back(Edge{v, cost});
        adj[v].push_back(Edge{u, cost});
    }

    Dijkstra(S, distS);
    Dijkstra(T, distT);
    Dijkstra(U, distU);
    Dijkstra(V, distV);

    for (int u = 1; u <= N; u++) {
        for (Edge e : adj[u]) {
            if (distS[u] + e.cost + distT[e.to] == distS[T]) {
                out[u].push_back(e.to);
                cntin[e.to]++;
            }
        }
    }

    queue <int> q;
    for (int u = 1; u <= N; u++) {
        if (cntin[u] == 0) {
            q.push(u);
        }
    }
    vector <int> topsort;
    while (q.empty() == false) {
        int u = q.front();
        q.pop();
        topsort.push_back(u);
        for (int v : out[u]) {
            if (--cntin[v] == 0) {
                q.push(v);
            }
        }
    }

    ll answer = LLONG_MAX;
    reverse(topsort.begin(), topsort.end());
    for (int u : topsort) {
        minU[u] = distU[u];
        minV[u] = distV[u];
        for (int v : out[u]) {
            minU[u] = min(minU[u], minU[v]);
            minV[u] = min(minV[u], minV[v]);
        }
        answer = min(answer, distU[u] + minV[u]);
        answer = min(answer, distV[u] + minU[u]);
    }
    cout << answer << "\n";

    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45