Submission #348579

#	Time	Username	Problem	Language	Result	Execution time	Memory
348579		Nima_Naderi	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	552 ms	41620 KiB

commuter_pass

 ///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 3e5 + 10;
const ll INF = 1e18;
ll n, m, sp, tp, up, vp;
ll dis[5][MXN], dp[5][MXN], val[MXN];
bool mark[MXN];
vector<ll> adj[MXN], Ver;
vector<pair<ll, ll>> G[MXN];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
void DIJ(ll f, ll src){
    for(int i = 1; i <= n; i ++){
        dis[f][i] = INF, mark[i] = 0;
    }
    dis[f][src] = 0, pq.push({0, src});
    while(!pq.empty()){
        ll u, d; tie(d, u) = pq.top();
        pq.pop();
        if(mark[u]) continue;
        mark[u] = 1;
        for(auto Pr : G[u]){
            ll v, w; tie(v, w) = Pr;
            if(!mark[v] && d + w < dis[f][v]){
                dis[f][v] = d + w;
                pq.push({dis[f][v], v});
            }
        }
    }
}
void Build(ll f, ll src, ll base){
    for(int i = 1; i <= n; i ++) adj[i].clear();
    for(int i = 1; i <= n; i ++) val[i] = dis[base][i];
    for(int u = 1; u <= n; u ++){
        for(auto Pr : G[u]){
            ll v, w; tie(v, w) = Pr;
            if(dis[f][v] + w == dis[f][u]){
                adj[u].push_back(v);
            }
        }
    }
}
bool cmpf;
bool CMP(ll u, ll v){
    return dis[cmpf][u] < dis[cmpf][v];
}
void Calc(ll f, ll base){
    for(int i = 1; i <= n; i ++) dp[f][i] = INF;
    cmpf = base;
    sort(Ver.begin(), Ver.end(), CMP);
    for(auto u : Ver){
        dp[f][u] = val[u];
        for(auto v : adj[u]){
            dp[f][u] = min(dp[f][u], dp[f][v]);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m >> sp >> tp >> up >> vp;
    for(int i = 1; i <= m; i ++){
        ll u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
        Ver.push_back(i);
    }
    DIJ(0, sp), DIJ(1, tp), DIJ(2, up), DIJ(3, vp);
    Build(0, sp, 2);//up
    Calc(0, 0);
    Build(0, sp, 3);//vp
    Calc(1, 0);
    Build(1, tp, 2);//up
    Calc(2, 1);
    Build(1, tp, 3);//vp
    Calc(3, 1);
    ll ans = dis[2][vp];
    for(int x = 1; x <= n; x ++){
        if(dis[0][x] + dis[1][x] > dis[0][tp]) continue;
        ll now = dis[2][x] + min(dp[1][x], dp[3][x]);
        ans = min(ans, now);
    }
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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