Submission #1281999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281999		Faisal_Saqib	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	257 ms	28168 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+100;
const ll inf=1e18;
ll du[N],dv[N];
vector<ll> ds[N],dt[N];
vector<pair<long long,int>> ma[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    int s,t;
    cin>>s>>t;
    int u,v;
    cin>>u>>v;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        ma[a].push_back({c,b});
        ma[b].push_back({c,a});
    }
    auto compute = [&]()
    {
        for(int i=0;i<=n;i++)
        {
            dv[i]=du[i];
            du[i]=inf;
        }
        du[u]=0;
        priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>> pq;
        pq.push({0,u});
        while(pq.size())
        {
            auto it=pq.top();
            pq.pop();
            if(du[it[1]]!=it[0])continue;
            for(auto tl:ma[it[1]])
            {
                int w=tl.first,q=tl.second;
                if(du[q]>it[0]+w)
                {
                    du[q]=it[0]+w;
                    pq.push({du[q],q});
                }
            }
        }
    };
    compute();
    swap(u,v);
    compute();
    auto compute_ = [&]()
    {
        for(int i=0;i<=n;i++)
        {
            dt[i]=ds[i];
            ds[i]={inf,inf,inf};
        }
        ds[s]={0,dv[s]+du[s],du[s]};
        priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>> pq;
        pq.push({0,dv[s]+du[s],du[s],s});
        while(pq.size())
        {
            auto it=pq.top();
            pq.pop();
            int x=it[3];
            it.pop_back();
            auto og=it;
            if(ds[x]!=it)continue;
            for(auto tl:ma[x])
            {
                it=og;
                int w=tl.first,q=tl.second;
                it[0]+=w;
                it[2]=min(du[q],og[2]);
                it[1]=min(og[1]-og[2],dv[q])+it[2];
                if(ds[q]>it)
                {
                    ds[q]=it;
                    pq.push({it[0],it[1],it[2],q});
                }
            }
        }
    };
    compute_();
    cout<<min(dv[u],ds[t][1])<<endl;
    return 0;
}

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