Submission #387097

#	Time	Username	Problem	Language	Result	Execution time	Memory
387097		Kepha	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	748 ms	27512 KiB

commuter_pass

// JOI 2017/2018 Commuter Pass
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define MX 100000
using namespace std;

int N, M, S, T, U, V;
vector<pair<int, int> > edges[MX + 1];
int distU[MX + 1], distV[MX + 1], distS[MX + 1];
int dpU[MX + 1], dpV[MX + 1];
bool visited[MX + 1];

void dij1(int src, int dist[]) {
    memset(visited, 0, sizeof(visited));
    fill(dist + 1, dist + 1 + N, INF);
    priority_queue<pair<int, int> > q;

    dist[src] = 0;
    q.push({0, src});

    while (q.size()) {
        int node = q.top().second;
        q.pop();

        if (visited[node]) continue;
        visited[node] = true;

        for (auto& i : edges[node]) {
            if (dist[node] + i.second < dist[i.first]) {
                dist[i.first] = dist[node] + i.second;
                q.push({-dist[i.first], i.first});
            }
        }
    }
}

int dij2(int src, int end) {
    fill(dpU, dpU + 1 + N, INF);
    fill(dpV, dpV + 1 + N, INF);
    memset(visited, 0, sizeof(visited));

    // distance, node, parent
    priority_queue<pair<int, pair<int, int> > > q;
    q.push({0, {src, 0}});

    while (q.size()) {
        int dist = q.top().first;
        int node = q.top().second.first, parent = q.top().second.second;
        q.pop();

        if (!visited[node]) {
            visited[node] = true;
            distS[node] = -dist;

            dpU[node] = min(dpU[parent], distU[node]);
            dpV[node] = min(dpV[parent], distV[node]);

            for (auto& i : edges[node])
                q.push({dist - i.second, {i.first, node}});
        }
        else if (-dist == distS[node]) {
            if (min(distU[node], dpU[parent]) + min(distV[node], dpV[parent])
                < dpU[node] + dpV[node]) {
                dpU[node] = min(distU[node], dpU[parent]);
                dpV[node] = min(distV[node], dpV[parent]);
            }
        }
    }
    
    return dpU[end] + dpV[end];
}

signed main() {
    // ifstream cin("tmp");

    cin >> N >> M >> S >> T >> U >> V;

    for (int i = 1; i <= M; i++) {
        int a, b, c; cin >> a >> b >> c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }

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

    int ans = distU[V];

    ans = min(ans, dij2(S, T));
    ans = min(ans, dij2(T, S));

    cout << ans << "\n";
    return 0;
}

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