제출 #357643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
357643		cute_hater	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	403 ms	26432 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];
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 });
            }
    }
}

bool reach(int v, int f) {
    if (v == f)
        return true;
    used[v] = 1;
    for (int u : ng[v])
        if (!used[u] && reach(u, f))
            return true;
    return false;
}

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) {
            good[u] = good[v] = 1;
            ng[u].pb(v);
        }
        if (dist[0][v] + c + dist[1][u] == len) {
            good[u] = good[v] = 1;
            ng[v].pb(u);
        }
    }
    int ans = dist[3][a];
    if (s == a) {
        loop1(i, n)
            if (good[i])
                ans = min(ans, dist[3][i]);
    }
    else if (n > 300) {
        int cla = s, clb = s;
        loop1(i, n)
            if (good[i]) {
                if (dist[2][cla] > dist[2][i])
                    cla = i;
                if (dist[3][clb] > dist[3][i])
                    clb = i;
            }
        ans = min(ans, dist[2][cla] + dist[3][clb]);
    }
    else {
        loop1(i, n)
            loop1(j, n) 
            if (good[i] && good[j] && reach(i, j)) {
                loop1(k, n)
                    used[k] = 0;
                ans = min({ ans, dist[2][i] + dist[3][j], dist[2][j] + dist[3][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: 0 / 24
• Subtask 4: 0 / 45