Submission #446468

#	Time	Username	Problem	Language	Result	Execution time	Memory
446468		anmolagarwal	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	335 ms	22412 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#include <iostream>

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}; // trick to explore an implicit 2D grid
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; // S,SE,E,NE,N,NW,W,SW neighbors  //GO FOR EVEN FOR 4 moves
char ch[] = {'U', '!', 'L', '!', 'D', '!', 'R', '!'};
#define fastinput                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

const int M = 1e5 + 1;
vector<pair<LL, int>> adj[M];
LL n;
const LL INF = LONG_LONG_MAX;
vector<LL> d_algo(int src)
{
    vector<LL> dis(n + 1, INF);
    vector<bool> processed(n + 1, false);
    using T = pair<LL, int>;
    priority_queue<T, vector<T>, greater<>> q;
    dis[src] = 0;
    q.push({0, src});
    while (!q.empty())
    {
        auto ptr = q.top();
        LL node, dis_now;
        tie(dis_now, node) = ptr;
        q.pop();
        if (processed[node])
        {
            continue;
        }
        processed[node] = true;
        for (const auto &x : adj[node])
        {
            int c = x.first;
            LL wt = x.second;
            LL poss = wt + dis_now;
            if (poss < dis[c])
            {
                dis[c] = poss;
                q.push({dis[c], c});
            }
        }
    }
    return dis;
}
int main()
{
    fastinput;
    LL m, i, j, tc, k;
    //messi

    cin >> n >> m;
    LL src1, src2, dest1, dest2;
    cin >> src1 >> dest1;
    cin >> src2 >> dest2;

    while (m--)
    {
        cin >> i >> j >> k;
        adj[i].pb({j, k});
        swap(i, j);
        adj[i].pb({j, k});
    }

    vector<LL> dis1 = d_algo(src1);
    vector<LL> dis2 = d_algo(dest1);

    ///////////////////////////////////////
    int src = src2;
    vector<LL> dis(n + 1, INF);
    vector<bool> processed(n + 1, false);
    using T = pair<LL, int>;
    priority_queue<T, vector<T>, greater<>> q;
    dis[src] = 0;
    q.push({0, src});

    auto nice = [&](int n1, int n2, LL wt)
    {
        if (dis1[n1] + dis2[n2] + wt == dis1[dest1])
        {
            return true;
        }

        swap(n1, n2);
        if (dis1[n1] + dis2[n2] + wt == dis1[dest1])
        {
            return true;
        }
        return false;
    };
    while (!q.empty())
    {
        auto ptr = q.top();
        LL node, dis_now;
        tie(dis_now, node) = ptr;
        q.pop();
        if (processed[node])
        {
            continue;
        }
        processed[node] = true;
        for (const auto &x : adj[node])
        {
            int c = x.first;
            LL wt = x.second;
            if (nice(node, c, wt))
            {
                wt = 0;
            }
            LL poss = wt + dis_now;
            if (poss < dis[c])
            {
                dis[c] = poss;
                q.push({dis[c], c});
            }
        }
    }
    /////////////////////////////////////////
    // debug(dis[dest2]);

    // for (i = 1; i <= n; i++)
    // {
    //     cout << "dis " << i << " = " << dis[i] << endl;
    // }

    cout << dis[dest2] << endl;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:59:17: warning: unused variable 'tc' [-Wunused-variable]
   59 |     LL m, i, j, tc, k;
      |                 ^~

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