제출 #1282946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282946		smileyboi	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	183 ms	16108 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;

#define __SmileyBoi__ int main()
#define __CodeKhongBug__ ios_base::sync_with_stdio(0);cin.tie(0);
#define all(v) v.begin(),v.end()
#define eb emplace_back

const int MAXN = 1e5 + 5;
const ll INF = 2e18;

int n,m;

vector<pii> e[MAXN];
ll du[MAXN],dv[MAXN],ans = INF;

void dijkstra(int s,ll d[]){
    fill(d + 1,d + n + 1,INF);
    d[s] = 0;
    priority_queue<pli,vector<pli>,greater<>> pq;
    pq.emplace(d[s],s);
    while(pq.size()){
        pli p = pq.top();pq.pop();
        ll dist = p.first;
        int u = p.second;
        if(dist != d[u]) continue;
        for(pii t : e[u]){
            int v = t.first,w = t.second;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                pq.emplace(d[v],v);
            }
        }
    }
}

ll d[MAXN],best_du[MAXN],best_dv[MAXN];

void calc(int S,int T){
    fill(d + 1,d + n + 1,INF);
    fill(best_du + 1,best_du + n + 1,INF);
    fill(best_dv + 1,best_dv + n + 1,INF);
    d[S] = 0;
    best_du[S] = du[S];
    best_dv[S] = dv[S];
    priority_queue<pli,vector<pli>,greater<>> pq;
    pq.emplace(d[S],S);
    while(pq.size()){
        pli p = pq.top();pq.pop();
        ll dist = p.first;
        int u = p.second;
        if(dist != d[u]) continue;
        for(pii t : e[u]){
            int v = t.first,w = t.second;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                best_du[v] = min(best_du[u],du[v]);
                best_dv[v] = min(best_dv[u],dv[v]);
                pq.emplace(d[v],v);
            }
            else if(d[v] == d[u] + w){
                if(min(best_du[u],du[v]) + min(best_dv[u],dv[v]) < best_du[v] + best_dv[v]){
                    best_du[v] = min(best_du[u],du[v]);
                    best_dv[v] = min(best_dv[u],dv[v]);
                    pq.emplace(d[v],v);
                }
            }
        }
    }
    ans = min(ans,best_du[T] + best_dv[T]);
}

__SmileyBoi__{
    __CodeKhongBug__

    int S,T,U,V;
    cin >> n >> m >> S >> T >> U >> V;
    for(int i = 1;i <= m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        e[u].eb(v,w);
        e[v].eb(u,w);
    }
    dijkstra(U,du);
    dijkstra(V,dv);
    ans = du[V];
    calc(S,T);
    calc(T,S);
    cout << ans;
}

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