Submission #897801

#	Time	Username	Problem	Language	Result	Execution time	Memory
897801		Newtech66	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	278 ms	24852 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol mod1=1e9+7,mod2=998244353,mod3=100000000000000003,hashpr=31;
const lol inf=9e18+8;
const double eps=1e-12;
const double PI=acos(-1.0);
const int N=1e5+5;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using ordered_set_type=lol;
typedef tree<ordered_set_type,null_type,less<ordered_set_type>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int,lol>> g[N];
vector<lol> d_s(N,inf),d_t(N,inf),d_u(N,inf),d_v(N,inf),m_s(N,inf),m_t(N,inf);
int n,m,s,t,u,v;

void shortest_path(int src,vector<lol>& d,vector<lol>& m,bool calc_m=false){
    //insert {-dist,v}
    priority_queue<pair<lol,int>> pq;
    pq.push({0,src});
    d[src]=0;
    if(calc_m)  m[src]=d_v[src];
    while(!pq.empty()){
        auto [ndist,u] = pq.top();
        pq.pop();
        if(-ndist>d[u])   continue;
        for(auto [v,w]:g[u]){
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                pq.push({-d[v],v});
                if(calc_m){
                    m[v]=min({m[u],d_v[v]});
                }
            }else if(d[u]+w==d[v]){
                lol old=m[v];
                if(calc_m){
                    m[v]=min({m[v],m[u],d_v[v]});
                }
                if(old!=m[v]){
                    pq.push({-d[v],v});
                }
            }
        }
    }
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
//cin>>_;
while(_--)
{
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=0;i<m;i++){
        lol a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    shortest_path(u,d_u,m_s);
    shortest_path(v,d_v,m_s);
    shortest_path(s,d_s,m_s,true);
    shortest_path(t,d_t,m_t,true);
    lol ans=inf;
    for(int i=1;i<=n;i++){
        if(d_s[i]+d_t[i]==d_s[t]){
            lol du=d_u[i];
            lol dv=min(m_s[i],m_t[i]);
            ans=min(ans,du+dv);
        }
    }
    cout<<min(d_u[v],ans);
}
return 0;
}

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