Submission #678719

#	Time	Username	Problem	Language	Result	Execution time	Memory
678719		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	432 ms	28028 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define ppll pair<pll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/"

ll n; vector <ll> Dis[2];
vector <pll> A[100005];
priority_queue <pll, vector <pll>, greater<pll>> q;
priority_queue <ppll, vector <ppll>, greater<ppll>> q2;

vector <ll> dijkstra(ll s)
{
    vector <ll> dis;
    dis.assign(n+1, 1e18);
    dis[s]=0; q.push({0, s});
    while (!q.empty())
    {
        ll u=q.top().se, disu=q.top().fi; q.pop();
        if (dis[u]!=disu)
            continue;
        for (pll i:A[u])
        {
            ll v=i.se, w=i.fi;
            if (dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                q.push({dis[v], v});
            }
        }
    }
    return dis;
}

vector <pll> dijkstra2(ll s, ll id)
{
    vector <pll> dis;
    dis.assign(n+1, {1e18, 1e18});
    dis[s]={0, Dis[id][s]}; q2.push({dis[s], s});
    while(!q2.empty())
    {
        ll u=q2.top().se;
        pll disu=q2.top().fi; q2.pop();
        if (disu!=dis[u])
            continue;
        // cout << u << " " << disu.fi << " " << disu.se << "\n";
        for (pll i:A[u])
        {
            ll v=i.se, w=i.fi;
            if (dis[u].fi+w<dis[v].fi)
            {
                dis[v].fi=dis[u].fi+w;
                dis[v].se=min(Dis[id][v], dis[u].se);
                q2.push({dis[v], v});
            }
            else if (dis[u].fi+w<=dis[v].fi)
            {
                if (dis[v].se>dis[u].se)
                {
                    dis[v].se=dis[u].se;    
                    q2.push({dis[v], v});
                }
            }
        }
    }
    // for (ll i=1; i<=n; i++)
    //     cout << dis[i].fi << " " << dis[i].se << "\n";
    return dis;
}

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    ll m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for (ll i=1; i<=m; i++)
    {
        ll u, v, w; cin >> u >> v >> w;
        A[u].pb({w, v}); A[v].pb({w, u});
    }
    Dis[0]=dijkstra(u); 
    Dis[1]=dijkstra(v);
    ll ans=Dis[0][v];
    vector <pll> s_u=dijkstra2(s, 0);
    vector <pll> s_v=dijkstra2(s, 1);
    vector <pll> t_u=dijkstra2(t, 0);
    vector <pll> t_v=dijkstra2(t, 1);
    for (ll i=1; i<=n; i++)
    {
        if (s_u[i].fi+t_v[i].fi!=s_u[t].fi)
            continue;
        ans=min(ans, s_u[i].se+t_v[i].se);
        ans=min(ans, s_v[i].se+t_u[i].se);
    }
    cout << ans;
}

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