Flipkart Taxi company (State & National highways)

PHOTO EMBED

Sun Jul 21 2024 16:25:54 GMT+0000 (Coordinated Universal Time)

Saved by @codestored #cpp

#include <bits/stdc++.h>
#define INF 10000000000
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i, n) for (long long int i = 0; i < n; i++)
#define FORR(i, a, b) for (int i = a; i < b; i++)
// think about a question calmly, don't get panic to solve A fast
// if after 10 mins you are unable to think anything see dashboard
using namespace std;

void djk_fun(vector<vector<vector<int>>> &adj, int src, vector<int> &dis)
{
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
    dis[src] = 0;
    pq.push({{0, src}});

    while (pq.size() > 0)
    {
        vector<int> vr = pq.top();
        pq.pop();

        int nod = vr[1];
        for (int i = 0; i < adj[nod].size(); i++)
        {
            int neg = adj[nod][i][0], wt = adj[nod][i][1];
            if (dis[nod] + wt < dis[neg])
            {
                dis[neg] = dis[nod] + wt;
                pq.push({dis[neg], neg});
            }
        }
    }
}

int short_path(vector<vector<vector<int>>> &adj, vector<vector<int>> &nh, int st, int en, int n)
{
    int m = nh.size(), ans = INT_MAX;
    // apply shortest path on src and dest
    vector<int> dis_src(n + 1, 1e9);
    vector<int> dis_dst(n + 1, 1e9);

    djk_fun(adj, st, dis_src);
    djk_fun(adj, en, dis_dst);

    for (int i = 0; i < m; i++)
    {
        int n1 = nh[i][0], n2 = nh[i][1], wt = nh[i][2];
        ans = min({ans, dis_src[n1] + wt + dis_dst[n2], dis_src[n2] + wt + dis_dst[n1]});
    }
    ans = min(ans, dis_src[en]);

    if(ans > 1e9)
    {
        return -1;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, m, st, en;
    cin >> n >> m;

    vector<vector<vector<int>>> adj(n + 1, vector<vector<int>>());
    vector<vector<int>> nh;

    // construct graph using state highways
    for (int i = 0; i < m; i++)
    {
        int u, v, st, nt;
        cin >> u >> v >> st >> nt;

        nh.pb({u, v, nt});
        adj[u].pb({v, st});
        adj[v].pb({u, st});
    }
    cin >> st >> en;

    cout << short_path(adj, nh, st, en, n) << endl;
    return 0;
}
content_copyCOPY