Submission #1308866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308866		kevin264	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2096 ms	33232 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;

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;
            }
        }
      }
    }
}

int dfs(vvi& g, vi& distu, vi& distv, int start, int end,int ans=INF, int a=INF, int b=INF){
a=min(a,distu[start]); b=min(b,distv[start]);
if (start==end) return min(ans,a+b); 
for(int i : g[start])
ans=min(ans,dfs(g, distu, distv,i, end, ans,a, b));

return ans;
}

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);
    cout<<min(distu[v], dfs(dag, distu, distv, s, t))<<endl; 
    return 0;
}

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