Submission #489749

#	Time	Username	Problem	Language	Result	Execution time	Memory
489749		AndrewZhang	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	400 ms	20152 KiB

commuter_pass

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45