Submission #1236597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236597		nasjes	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	409 ms	134332 KiB

commuter_pass

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 5*1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e18 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m;
vector<pll> a[dim];
ll dst1[dim], dst2[dim], dst3[dim], dst11[dim], dst22[dim];

int main() {
    ll k, s, t, u0, v0;
    cin>>n>>m;
    cin>>s>>t;
    cin>>u0>>v0;
    for(int i=1; i<=m; i++){
        ll x, y, w;
        cin>>x>>y>>w;
        a[x].pb({y, w});
        a[y].pb({x, w});
    }
    priority_queue<pll, vector<pll>, greater<pll>> q;
    for(int i=1; i<=n; i++){
        dst1[i]=inf;
        dst2[i]=inf;
        dst3[i]=inf;
        dst11[i]=inf;
        dst22[i]=inf;
    }
    dst1[u0]=0;
    q.push({0, u0});
    while(q.size()>0){
        ll v=q.top().se;
       // cout<<v<<endl;
        q.pop();
        for(auto x: a[v]){
            if(dst1[x.fi]>dst1[v]+x.se){
                dst1[x.fi]=dst1[v]+x.se;
                q.push({dst1[x.fi], x.fi});
            }
        }
    }
  //  cout<<dst1[6]<<endl;
    q.push({0, v0});
    dst2[v0]=0;
    while(q.size()>0){
        ll v=q.top().se;
        q.pop();
        for(auto x: a[v]){
            if(dst2[x.fi]>dst2[v]+x.se){
                dst2[x.fi]=dst2[v]+x.se;
                q.push({dst2[x.fi], x.fi});
            }
        }
    }
  //  cout<<dst2[1]<<endl;
    q.push({0, s});
    dst3[s]=0;
    dst11[s]=dst1[s];
    dst22[s]=dst2[s];
   while(q.size()>0){
        ll v=q.top().se;
        q.pop();
        for(auto x: a[v]){
            ll w=x.se;
            if(dst3[x.fi]==dst3[v]+w){
                if(dst22[x.fi] + dst11[x.fi]>=min(dst1[x.fi], dst11[v])+ min(dst2[x.fi], dst22[v])) {
                    dst11[x.fi] = min(dst1[x.fi], dst11[v]);
                    dst22[x.fi] = min(dst2[x.fi], dst22[v]);
                }
            }
            else if(dst3[x.fi]>dst3[v]+w){
                dst3[x.fi]=dst3[v]+w;
                q.push({dst3[x.fi], x.fi});
                dst11[x.fi]=min(dst1[x.fi], dst11[v]);
                dst22[x.fi]=min(dst2[x.fi], dst22[v]);
            }
        }

    }
    cout<<min(dst11[t]+dst22[t], dst1[v0])<<endl;
    return 0;
}

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