제출 #1319925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319925		asafe	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	361 ms	27360 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pair<int,int>>
#define vll vector<long long>
#define pb push_back
#define pll pair<long long ,long long>
#define pf push_front
#define ql cout<<endl;

#define int long long 
const ll inf=1e18;
const int maxn= 1e5+5;
int n,m,s,t,u,v;
int par[maxn];
vii g[maxn];
vll dists,distu,distv;
int dp[2][maxn];
bool bt[maxn];
int ans=inf;
void dijkstra(int start,vll &dist){
    dist.resize(n+1);
    priority_queue<pii,vii,greater<pii>> q;
    fill(dist.begin(),dist.end(),inf);
    dist[start]=0;
    q.push({0,start});
    fill(bt,bt+n+1,0);
    while(!q.empty()){
        auto[du,u]=q.top();
        q.pop();
        if(bt[u])continue;
        bt[u]=1;
        for(auto[viz , d] : g[u]){
            if (dist[viz] > du + d) {
                dist[viz] = du + d;
                q.push({dist[viz], viz});
            }
        }
    }

}

void dijkstra2(int start,int  end){
    fill(bt,bt+n+1,0);
    fill(dp[0],dp[0]+n+1,inf);
    fill(dp[1],dp[1]+n+1,inf);
    
    priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>q;
    
    q.push({0,{start,0}});
    dp[0][start]=distu[start];
    dp[1][start]=distu[start]+distv[start];
    while(!q.empty()){
        auto[du,p]=q.top();
        auto[u,paru]=p;
        q.pop();
        if (!bt[u]) {
            bt[u] = true;
            dists[u] = du;

            if (paru == 0) {
                dp[0][u] = distu[u];
                dp[1][u] = distu[u] + distv[u];
            } else {
                dp[0][u] = min(distu[u], dp[0][paru]);
                dp[1][u] = min(dp[0][u] + distv[u], dp[1][paru]);
            }

            for (auto [v, w] : g[u]) {
                q.push({du + w, {v, u}});
            }
        }
        else if (du == dists[u]) {
            dp[0][u] = min(dp[0][u], dp[0][paru]);
            dp[1][u] = min({dp[1][u], dp[0][u] + distv[u], dp[1][paru]});
        }
    }

    ans=min(ans,dp[1][end]);

}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>s>>t>>u>>v;

    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }

    dijkstra(u,distu);
    dijkstra(v,distv);
    
    ans=distu[v];
    dists.resize(n+1);
    dijkstra2(s,t);
    dijkstra2(t,s);

    cout<<ans;

}

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