Submission #357703

#	Time	Username	Problem	Language	Result	Execution time	Memory
357703		cute_hater	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	423 ms	31572 KiB

commuter_pass

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>


/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << -1; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const int N = 1e5 + 7, INF = 1e18;

vector <pi> g[N];
vector <int> ng[N];
int dist[4][N], dp[2][N];
ti ed[2 * N];
bool good[N], used[N];

void dijkstra(int fst, int f) {
    priority_queue <pi, vector <pi>, greater <pi> > q;
    q.push({ 0, fst });
    loop(i, N)
        dist[f][i] = INF;
    dist[f][fst] = 0;
    while (!q.empty()) {
        int v = q.top().S, dv = q.top().F;
        q.pop();
        if (dv > dist[f][v])
            continue;
        for (pi u : g[v])
            if (dist[f][u.F] > dist[f][v] + u.S) {
                dist[f][u.F] = dist[f][v] + u.S;
                q.push({ dist[f][u.F], u.F });
            }
    }
}

void dfs(int v, int a, int b) {
    used[v] = 1;
    dp[0][v] = dist[2][v];
    dp[1][v] = dist[3][v];
    for (int u : ng[v]) {
        if (!used[u])
            dfs(u, a, b);
        dp[0][v] = min(dp[0][v], dp[0][u]);
        dp[1][v] = min(dp[1][v], dp[1][u]);
    }
}

void solve() {
    int n, m, s, t, a, b;
    cin >> n >> m >> s >> t >> a >> b;
    loop(i, m) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].pb({ v, c });
        g[v].pb({ u, c });
        ed[i] = mkt(u, v, c);
    }
    dijkstra(s, 0);
    dijkstra(t, 1);
    dijkstra(a, 2);
    dijkstra(b, 3);
    int len = dist[0][t];
    loop(i, m) {
        int u, v, c;
        tie(u, v, c) = ed[i];
        if (dist[0][u] + c + dist[1][v] == len || dist[0][v] + c + dist[1][u] == len) {
            good[u] = good[v] = 1;
            if (dist[0][u] < dist[0][v])
                ng[u].pb(v);
            else
                ng[v].pb(u);
        }
    }
    int ans = dist[3][a];
    loop1(i, n) {
        if (good[i]) {
            if (!used[i])
                dfs(i, a, b);
            ans = min({ ans, dp[0][i] + dist[3][i], dp[1][i] + dist[2][i] });
        }
    }
    cout << ans;
}

signed main() {
    //freopen("b2.txt", "r", stdin);
    //freopen("ans9.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

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