Submission #525392

#	Time	Username	Problem	Language	Result	Execution time	Memory
525392		na2a	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	533 ms	68540 KiB

commuter_pass

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <unordered_set>

using namespace std;

#define pb push_back
#define pp pop_back
#define f first
#define s second
#define mp make_pair

const int N = (int) 1e6 + 123;

int n, m;
int S, T, U, V;

int edgeFrom[N];
int edgeTo[N];
int edgeWeight[N];

vector<int> g[N];
vector<int> dag[N];

long long d[4][N];

void dijkstra(long long *dist, int start) {
    for (int i = 1; i <= n; i++) dist[i] = (long long) 1e18;
    dist[start] = 0;
    set<pair<long long, int>> s;
    s.insert(make_pair(0, start));
    while (!s.empty()) {
        int v = s.begin() -> second;
        s.erase(s.begin());
        for (int edge : g[v]) {
            int to = ((edgeFrom[edge] ^ edgeTo[edge]) ^ v);
            if (dist[to] > dist[v] + edgeWeight[edge]) {
                s.erase(make_pair(dist[to], to));
                dist[to] = dist[v] + edgeWeight[edge];
                s.insert(make_pair(dist[to], to));
            }
        }
    }
}

bool used[N];
long long minU[N];
long long minV[N];

long long ans = 1e18;

void dfs(int v) {

    if (used[v]) return;

    used[v] = true;
    minU[v] = d[2][v];
    minV[v] = d[3][v];

    for (auto to : dag[v]) {
        dfs(to);
        minU[v] = min(minU[v], minU[to]);
        minV[v] = min(minV[v], minV[to]);
    }

    ans = min(ans, d[2][v] + minV[v]);
    ans = min(ans, d[3][v] + minU[v]);

}

int main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    cin >> S >> T;
    cin >> U >> V;

    for (int i = 1; i <= m; i++) {
        cin >> edgeFrom[i] >> edgeTo[i] >> edgeWeight[i];
        g[edgeFrom[i]].push_back(i);
        g[edgeTo[i]].push_back(i);
    }

    dijkstra(d[0], S);
    dijkstra(d[1], T);
    dijkstra(d[2], U);
    dijkstra(d[3], V);

    long long shortest = d[0][T];
    for (int i = 1; i <= m; i++) {
        if (d[0][edgeFrom[i]] + edgeWeight[i] + d[1][edgeTo[i]] == shortest) {
            dag[edgeFrom[i]].push_back(edgeTo[i]);
        } else if (d[0][edgeTo[i]] + edgeWeight[i] + d[1][edgeFrom[i]] == shortest) {
            dag[edgeTo[i]].push_back(edgeFrom[i]);
        }
    }

    dfs(S);

    cout << min(ans, d[2][V]);

    return 0;
}

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