제출 #669368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
669368		beedle	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	434 ms	26984 KiB

commuter_pass

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define ld long long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

vector <pair<ll,ll>> adj[100000+1];

void getdist(ll source, vector <ll> &d)
{
    set<pair<ll,ll>> s;
    s.insert({0,source});
    d[source]=0;

    while(!s.empty())
    {
        auto v=*s.begin();
        s.erase(v);

        for(auto u:adj[v.ss])
        if(d[u.ff]>v.ff+u.ss)
        {
            s.erase({d[u.ff],u.ff});
            d[u.ff]=v.ff+u.ss;
            s.insert({d[u.ff],u.ff});
        }
    }
}

signed main()
{
    fast;

    // freopen("curling.in","r",stdin);
    // freopen("curling.out","w",stdout);

    vector <ll> du(1e5+1,INF), dv(1e5+1,INF);

    ll n,m;
    cin>>n>>m;

    ll s,t,u,v;
    cin>>s>>t>>u>>v;

    rep(i,1,m)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }

    getdist(u,du);
    getdist(v,dv);

    set <pair<ll,ll>> st;
    vector <ll> d(n+1,INF);
    vector <ll> mindu(n+1);
    vector <ll> myscoreu(n+1);
    vector <ll> bestscoreu(n+1);

    vector <ll> mindv(n+1), myscorev(n+1), bestscorev(n+1);

    d[s]=0;
    mindu[s]=du[s];
    mindv[s]=dv[s];
    myscoreu[s]=myscorev[s]=bestscoreu[s]=bestscorev[s]=d[u]+dv[s];
    st.insert({0,s});

    while(!st.empty())
    {
        auto [dist, vertex]=*st.begin();
        st.erase({dist,vertex});

        for(auto u:adj[vertex])
        {
            if(d[u.ff]>dist+u.ss)
            {
                st.erase({d[u.ff],u.ff});
                d[u.ff]=dist+u.ss;
                st.insert({d[u.ff],u.ff});
                mindu[u.ff]=min(du[u.ff],mindu[vertex]);
                myscoreu[u.ff]=dv[u.ff]+mindu[u.ff];
                bestscoreu[u.ff]=min(myscoreu[u.ff],bestscoreu[vertex]);

                mindv[u.ff]=min(dv[u.ff],mindv[vertex]);
                myscorev[u.ff]=du[u.ff]+mindv[u.ff];
                bestscorev[u.ff]=min(myscorev[u.ff],bestscorev[vertex]);
            }
            else if(d[u.ff]==dist+u.ss)
            {
                st.insert({d[u.ff],u.ff});
                mindu[u.ff]=min({mindu[u.ff],mindu[vertex],du[u.ff]});
                myscoreu[u.ff]=min(myscoreu[u.ff], dv[u.ff]+mindu[u.ff]);
                bestscoreu[u.ff]=min({myscoreu[u.ff], bestscoreu[vertex], bestscoreu[u.ff]});

                mindv[u.ff]=min({mindv[u.ff],mindv[vertex],dv[u.ff]});
                myscorev[u.ff]=min(myscorev[u.ff], du[u.ff]+mindv[u.ff]);
                bestscorev[u.ff]=min({myscorev[u.ff], bestscorev[vertex], bestscorev[u.ff]});
            }
        }
    }

    cout<<min(bestscoreu[t], bestscorev[t])<<endl;

    return 0;  
}

/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

8 8 
5 7 
6 8 
1 2 2 
2 3 3
3 4 4
1 4 1 
1 5 5 
2 6 6 
3 7 7 
4 8 8

5 5 
1 5 
2 3 
1 2 1 
2 3 10 
2 4 10
3 5 10
4 5 10
*/

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