Submission #669358

#	Time	Username	Problem	Language	Result	Execution time	Memory
669358		beedle	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2085 ms	16888 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];
vector <ll> du(1e5+1,INF), dv(1e5+1,INF);

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.rbegin();
        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);

    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.rbegin();
    //     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;

    cout<<1<<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: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45