제출 #678601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678601		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	301 ms	33416 KiB

commuter_pass

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 300005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k, s, t, u, v, m;

int du[maxN];
int dv[maxN];
int ds[maxN];
int dt[maxN];
int dp[maxN][4];
vector<ii> vc[maxN];

int ans = oo;
int best;

void dijis(int root, int* ds, bool exec = 0){
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for1(i, 0, n) ds[i] = oo;
    ds[root] = 0; pq.push(ii(0, root));
    while(!pq.empty()){
        ii pr = pq.top(); pq.pop();
        int node = pr.se, dist = pr.fi;
        if(ds[node] == dist){
            // cout << node << " " << dist << endl;
            bool suu = (exec && ds[node] + dt[node] == best);
            if(suu){
                // cout << node << " " << dist << endl;
                for1(mask, 0, 3) for1(i, 1, 2){
                    int targ = mask | i;
                    int &f = dp[node][targ];
                    if(i == 1) f = min(f, dp[node][mask] + du[node]);
                    if(i == 2) f = min(f, dp[node][mask] + dv[node]);
                }
            }
            for(ii cc : vc[node]){
                int targ = cc.fi + dist;
                if(ds[cc.se] > targ){
                    ds[cc.se] = targ;
                    pq.push(ii(targ, cc.se));
                }
                if(suu && ds[cc.se] == targ){
                    // cout << node << " " << cc.se << endl;
                    for1(mask, 0, 3){
                        dp[cc.se][mask] = min(dp[cc.se][mask], dp[node][mask]);
                    }
                }

            }
        }
    }
}

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    for1(i, 1, m){
        cin >> x >> y >> z;
        vc[x].pb(ii(z, y));
        vc[y].pb(ii(z, x));
    }
    memset(dp, 15, sizeof(dp));
    dijis(u, du);
    dijis(v, dv);
    ans = min(ans, du[v]);
    dijis(t, dt);
    best = dt[s];
    dp[s][0] = 0;
    dijis(s, ds, 1);
    ans = min(ans, dp[t][3]);
    cout << ans << endl;
}

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