13 months ago

hadeso-0 • 40

Mumbai

// Question 3 : Taxi Company 

ll n, m;

cin >> n >> m;

vector<vector<ll>> eds(m, vector<ll>(4, 0));

vector<vector<vector<ll>>> gr(n + 1);

for (ll i = 0; i < m; ++i) {

    cin >> eds[i][0] >> eds[i][1] >> eds[i][2] >> eds[i][3];

    gr[eds[i][0]].push_back({ eds[i][1], eds[i][2], eds[i][3] });

    gr[eds[i][1]].push_back({ eds[i][0], eds[i][2], eds[i][3] });

}

ll src, des;

cin >> src >> des;

priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> pq;

vector<vector<ll>> dp(n + 1, vector<ll>(2, 1e18));

dp[src][0] = 0;

dp[src][1] = 0;

if (src == des) {

    cout << 0;

    return;

}

// dist, node, NatHwyLeft

pq.push({ 0, src, 1 });

while (!pq.empty()) {

    ll node = pq.top()[1];

    ll dist = pq.top()[0];

    ll NatLeft = pq.top()[2];

    pq.pop();

    for (auto& ch : gr[node]) {

        ll nex = ch[0]; ll stDis = ch[1]; ll natDis = ch[2];

        if (NatLeft == 1) {

            if (dp[nex][1] > dist + stDis) {

                dp[nex][1] = dist + stDis;

                pq.push({ dp[nex][1], nex, 1 });

            }

            if (dp[nex][0] > dist + natDis) {

                dp[nex][0] = dist + natDis;

                pq.push({ dp[nex][0], nex, 0 });

            }

        }

        else {

            if (dp[nex][0] > dist + stDis) {

                dp[nex][0] = dist + stDis;

                pq.push({ dp[nex][0], nex, 0 });

            }

        }

    }

}

ll ans = min(dp[des][0], dp[des][1]);

if (ans == INT_MAX) {

    cout << -1;

}

else {

    cout << ans;

}