Submission #653303

#	Time	Username	Problem	Language	Result	Execution time	Memory
653303		TitanSlayer	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	686 ms	36400 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ld long double
#define vv vector
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define mod 1000000007

typedef pair<ll, ll> pll;
typedef vv<ll> vll;
typedef vv<ld> vld;
typedef vv<pll> vpll;
typedef set<ll>::iterator sitr;

#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
///////////////////////////////////

ll inf = 1e17;

void dijkstra(ll node, vll &dist, vv<vpll> &g)
{
    priority_queue<pll, vpll, greater<pll>> mh;
    mh.push({0, node});

    while (!mh.empty())
    {
        pll t = mh.top();
        mh.pop();

        if (dist[t.S] != inf)
            continue;
        dist[t.S] = t.F;
        for (ll i = 0; i < g[t.S].size(); i++)
            mh.push({t.F + g[t.S][i].S, g[t.S][i].F});
    }
}

void dfs(ll node, vll &dist1, vll &dist2, vll &vis, vv<vpll> &g, vll &top_sort, vv<vll> &valid_child_g, vv<vll> &valid_par_g, ll t)
{
    if (vis[node])
        return;
    vis[node] = 1;
    for (ll i = 0; i < g[node].size(); i++)
    {
        if (dist1[node] + g[node][i].S + dist2[g[node][i].F] == dist1[t])
        {
            dfs(g[node][i].F, dist1, dist2, vis, g, top_sort, valid_child_g, valid_par_g, t);
            valid_child_g[node].pb(g[node][i].F);
            valid_par_g[g[node][i].F].pb(node);
        }
    }
    top_sort.pb(node);
}

int main()
{
    fastio;
    ll T = 1;
    // cin >> T;
    while (T--)
    {
        ll i, j, a, b, c, n, m, u, v, s, t, node;
        cin >> n >> m;
        cin >> s >> t;
        cin >> u >> v;

        vv<vpll> g(n + 1);
        vv<vll> valid_child_g(n + 1), valid_par_g(n + 1);
        for (i = 0; i < m; i++)
        {
            cin >> a >> b >> c;
            g[a].pb({b, c});
            g[b].pb({a, c});
        }

        vll dS(n + 1, inf), dU(n + 1, inf), dV(n + 1, inf), dT(n + 1, inf);
        dijkstra(s, dS, g);
        dijkstra(u, dU, g);
        dijkstra(v, dV, g);
        dijkstra(t, dT, g);

        vll vis(n + 1, 0), top_sort;
        dfs(s, dS, dT, vis, g, top_sort, valid_child_g, valid_par_g, t);
        reverse(top_sort.begin(), top_sort.end());

        // for (i = 1; i <= n; i++)
        // {
        //     cout << i << ": ";
        //     for (j = 0; j < valid_child_g[i].size(); j++)
        //         cout << valid_child_g[i][j] << " ";
        //     cout << endl;
        // }

        // for (i = 1; i <= n; i++)
        // {
        //     cout << i << ": ";
        //     for (j = 0; j < valid_par_g[i].size(); j++)
        //         cout << valid_par_g[i][j] << " ";
        //     cout << endl;
        // }

        vll dp_child(n + 1, inf), dp_ancestor(n + 1, inf);
        for (i = top_sort.size() - 1; i >= 0; i--)
        {
            node = top_sort[i];
            dp_child[node] = dV[node];
            for (j = 0; j < valid_child_g[node].size(); j++)
                dp_child[node] = min(dp_child[node], dp_child[valid_child_g[node][j]]);
        }

        for (i = 0; i < top_sort.size(); i++)
        {
            node = top_sort[i];
            dp_ancestor[node] = dV[node];
            for (j = 0; j < valid_par_g[node].size(); j++)
                dp_ancestor[node] = min(dp_ancestor[node], dp_ancestor[valid_par_g[node][j]]);
        }

        // //
        // cout << endl;
        // for (i = 1; i <= n; i++)
        //     cout << dS[i] << " " << dU[i] << " " << dV[i] << " " << dT[i] << endl;
        // cout << endl;

        // for (auto i : top_sort)
        //     cout << i << " ";
        // cout << endl;

        // for (i = 1; i <= n; i++)
        //     cout << dp_child[i] << " ";
        // cout << endl;
        // for (i = 1; i <= n; i++)
        //     cout << dp_ancestor[i] << " ";
        // cout << endl;
        // //

        ll ans = dU[v];
        for (i = 0; i < top_sort.size(); i++)
            ans = min({ans, dU[top_sort[i]] + dp_child[top_sort[i]],
                       dU[top_sort[i]] + dp_ancestor[top_sort[i]]});
        cout << ans << endl;
    }
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int, vll&, std::vector<std::vector<std::pair<long long int, long long int> > >&)':
commuter_pass.cpp:38:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (ll i = 0; i < g[t.S].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int, vll&, vll&, vll&, std::vector<std::vector<std::pair<long long int, long long int> > >&, vll&, std::vector<std::vector<long long int> >&, std::vector<std::vector<long long int> >&, long long int)':
commuter_pass.cpp:48:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (ll i = 0; i < g[node].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:112:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for (j = 0; j < valid_child_g[node].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:116:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (i = 0; i < top_sort.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:120:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             for (j = 0; j < valid_par_g[node].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:143:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         for (i = 0; i < top_sort.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~

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