Submission #1308887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308887		kevin264	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	197 ms	33236 KiB

commuter_pass

#include "bits/stdc++.h"

using namespace std;
#define int long long
#define endl '\n'
#define sz(x) (int)(x.size()) 
#define ff first
#define ss second
#define m_p make_pair
#define INF LLONG_MAX
#define OO LLONG_MAX
using vi=vector<int>;
using vvi=vector<vi>; 
using pii=pair<int,int>; 
template<typename T> using inverse_pq = priority_queue<T,vector<T>, greater<T> >; 
template<typename T=int> void cin_vector(vector<T> &v) {for(int& i : v) cin>>i;}
vvi void_vector=vvi();

void djikstra(vector<vector<pii> >& g, vi& dist, int start, int end=-1, vvi& dag=void_vector){
    inverse_pq<pii> pq; 
    vvi father(g.size()); 
    vector<bool> mark(g.size(),false); 
    pq.push({0,start}); 
    dist[start]=0;
    while(!pq.empty()){ 
        int top=pq.top().ss; pq.pop(); 
        if(mark[top]) continue;
        mark[top]=true;
           for(auto i : g[top]){
            int d=i.ss+dist[top];
            if(d==dist[i.ff]){
                father[i.ff].push_back(top); 
            }else if(d<dist[i.ff]){
                vector<int> aux(1,top); 
                dist[i.ff]=d;
                father[i.ff].swap(aux); 
                pq.push({d,i.ff}); 
            }
        }
    }

    if(end!=-1){ 
      queue<int> q;
      vector<bool> v(dag.size(), false);
      q.push(end); 
      v[end]=true;
      while(!q.empty()){
        int top=q.front(); q.pop(); 
        for(int i : father[top]){
            dag[i].push_back(top); 
            if(!v[i]){
                q.push(i);
                v[i]=true;
            }
        }
      }
    }
}

void dfs(vvi& g, vi& distu, vi& distv, vector<pair<int,pii>>& nemo, int start){
int a=distu[start]; int b=distv[start];
nemo[start].ss.ff=a; nemo[start].ss.ss=b;
nemo[start].ff=a+b;
for(int i : g[start]){
if(nemo[i].ff==INF){
dfs(g, distu, distv,nemo, i);
}
nemo[start].ff=min(nemo[start].ff, min(a+nemo[i].ss.ss,b+nemo[i].ss.ff));
nemo[start].ss.ff=min(nemo[start].ss.ff,nemo[i].ss.ff); 
nemo[start].ss.ss=min(nemo[start].ss.ss,nemo[i].ss.ss); 
}
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0); 
    int n,m;
    cin>>n>>m;
    int s,t,u,v; 
    cin>>s>>t>>u>>v;
    vector<vector<pii> > g(n+1);
    while(m--){
     int a,b,w;
     cin>>a>>b>>w;
     g[a].push_back(m_p(b,w));
     g[b].push_back(m_p(a,w));
    }
    vi dist(n+1, INF), distu(n+1, INF), distv(n+1, INF);
    vvi dag(n+1); 
    djikstra(g,distu, u);
    djikstra(g,distv, v);
    djikstra(g,dist, s, t, dag);
    vector<pair<int,pii>> nemo(n+1,m_p(INF,m_p(INF,INF)));
    dfs(dag, distu, distv, nemo, s) ; 
    int ans=INF;
    for(auto i : nemo) ans=min(ans,i.ff); 
    cout<<min(distu[v], ans)<<endl; 
    return 0;
}

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