제출 #1180439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180439		user736482	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	689 ms	61616 KiB

commuter_pass

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,q,s,t,a,b,c,d,ans=INFL,bst,k,e,m,pier,h,w,u,v;
ll dst[300007],dst2[300007];
bool odw[300007],odw2[300007];
vector<pair<ll,ll>>g2[100007],g[300007];//dst,gdzie
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s>>t>>u>>v;
    s--;
    t--;
    u--;
    v--;
    for(ll i=0;i<m;i++){
        cin>>a>>b>>c;
        a--;
        b--;
        g2[a].pb({c,b});
        g2[b].pb({c,a});
    }
    pq.push({0,s});
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw[pom.ss])continue;
        odw[pom.ss]=1;
        dst[pom.ss]=pom.ff;
        for(auto i : g2[pom.ss]){
            pq.push({pom.ff+i.ff,i.ss});
        }
    }
    pq.push({0,t});
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw2[pom.ss])continue;
        odw2[pom.ss]=1;
        dst2[pom.ss]=pom.ff;
        for(auto i : g2[pom.ss]){
            pq.push({pom.ff+i.ff,i.ss});
        }
    }
    ll mn=dst[t];
    for(ll i=0;i<n;i++){
        for(auto j : g2[i]){
            if(mn==j.ff+dst[i]+dst2[j.ss]){
                g[i+n].pb({0,j.ss+n});
            }
            else{
            }
        }
    }
    for(ll i=0;i<n;i++){
        odw[i]=0;
        odw2[i]=0;
        g[i].pb({0,i+n});
        g[i+n].pb({0,i+2*n});
        for(pair<ll,ll>j : g2[i]){
            g[i].pb(j);
            g[i+2*n].pb({j.ff,j.ss+2*n});
        }
    }
    pq.push({0,u});
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw[pom.ss])continue;
        odw[pom.ss]=1;
        dst[pom.ss]=pom.ff;
        for(auto i : g[pom.ss]){
            pq.push({pom.ff+i.ff,i.ss});
        }
    }
    pq.push({0,v});
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(odw2[pom.ss])continue;
        odw2[pom.ss]=1;
        dst2[pom.ss]=pom.ff;
        for(auto i : g[pom.ss]){
            pq.push({pom.ff+i.ff,i.ss});
        }
    }
    cout<<min(dst[v+2*n],dst2[u+2*n]);
    
}

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