Submission #1180417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180417		user736482	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	306 ms	27304 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
#define MX 507

ll n,q,s,t,a,b,c,d,ans=INFL,bst,k,e,m,pier,h,w,u,v;

ll dst[100007],dst2[100007];
bool odw[100007],odw2[100007],odw3[100007];
vector<pair<ll,ll>>g[100007],g2[100007];//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]){
                g2[i].pb({0,j.ss});
                //cout<<i<<" "<<j.ss<<"\n";
            }
            else{
            //    cout<<2;
            }
        }
    }
    for(ll i=0;i<n;i++){
        odw[i]=0;
        odw2[i]=0;
    }
    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 : g2[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 : g2[pom.ss]){
            pq.push({pom.ff+i.ff,i.ss});
        }
    }
    cout<<min(dst[v],dst2[u]);
    
    
}

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