oj.uz

Submission #669368

# Submission time Handle Problem Language Result Execution time Memory
669368 2022-12-06T10:10:24 Z beedle Commuter Pass (JOI18_commuter_pass) C++17
16 / 100
 434 ms 26984 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 23032 KB Output is correct
2 Correct 357 ms 25600 KB Output is correct
3 Correct 365 ms 25708 KB Output is correct
4 Correct 415 ms 26876 KB Output is correct
5 Correct 341 ms 25548 KB Output is correct
6 Correct 421 ms 26984 KB Output is correct
7 Correct 363 ms 25488 KB Output is correct
8 Correct 355 ms 25652 KB Output is correct
9 Correct 385 ms 26604 KB Output is correct
10 Correct 284 ms 26644 KB Output is correct
11 Correct 122 ms 17068 KB Output is correct
12 Correct 399 ms 26140 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 22532 KB Output is correct
2 Correct 397 ms 25324 KB Output is correct
3 Incorrect 392 ms 25200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5588 KB Output is correct
2 Incorrect 3 ms 4260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 23032 KB Output is correct
2 Correct 357 ms 25600 KB Output is correct
3 Correct 365 ms 25708 KB Output is correct
4 Correct 415 ms 26876 KB Output is correct
5 Correct 341 ms 25548 KB Output is correct
6 Correct 421 ms 26984 KB Output is correct
7 Correct 363 ms 25488 KB Output is correct
8 Correct 355 ms 25652 KB Output is correct
9 Correct 385 ms 26604 KB Output is correct
10 Correct 284 ms 26644 KB Output is correct
11 Correct 122 ms 17068 KB Output is correct
12 Correct 399 ms 26140 KB Output is correct
13 Correct 394 ms 22532 KB Output is correct
14 Correct 397 ms 25324 KB Output is correct
15 Incorrect 392 ms 25200 KB Output isn't correct
16 Halted 0 ms 0 KB -