제출 #814502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
814502		akari	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	358 ms	26332 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<ll,ll>
const ll maxn=2e5+2,inf=1e16;

int n,m,s,t,op,ed;
vector<ll> d1,d2,t1,t2;
vector<ii> adj[maxn];
vector<ll> g[maxn];
vector<int> ver;
bool ok[maxn];
bool pass[maxn];
ll ans=inf;
ll dp[maxn];

void dij(int st, vector<ll> &dis){
    dis.resize(n+2,inf);
    priority_queue <ii,vector<ii>,greater<ii>> pq;
    pq.push({0,st});
    dis[st]=0;
    while(!pq.empty()){
        int u=pq.top().se;
        int d=pq.top().fi;
        pq.pop();
        if (dis[u]<d) continue;
        for (ii v:adj[u]){
            if (dis[v.fi]>dis[u]+v.se){
                dis[v.fi]=dis[u]+v.se;
                pq.push({dis[v.fi],v.fi});
            }
        }
    }
}

int main(){
    cin>>n>>m>>s>>t>>op>>ed;
    while (m--){
        int a,b,c; cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dij(s,d1);
    dij(t,d2);
    dij(op,t1);
    dij(ed,t2);
    for (int i=1;i<=n;++i){
        dp[i]=inf;
        if (d1[i]+d2[i] == d1[t]){
            ver.push_back(i);
            ok[i]=1;
        } 
    }
    if (s==op){
        for (int i:ver){
            ans=min(ans,t2[i]);
        }
        cout<<ans;
        return 0;
    }
    for (int i: ver){
        for (ii x: adj[i]) if (ok[x.fi]) g[i].push_back(x.fi);
    }
    queue<ii> qu;
    qu.push({s,s});
    pass[s]=1;
    while (!qu.empty()){
        int u=qu.front().fi;
        int p=qu.front().se;
        //cout<<u<<endl;
        qu.pop();
        dp[u]=min(dp[p],t2[u]);
        for (int v: g[u]){
            dp[v]=min(dp[u],t2[v]);
            if (pass[v]==0){
                pass[v]=1;
                qu.push({v,u});
            }
        }    
    }
    for (int u:ver) ans=min(ans,t1[u]+dp[u]);
    //for (int i:ver) cout<<i<<" "<<dp[i]<<endl;  
    cout<<min(ans,t1[ed]);
}

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