Flight Discount

Your task is to find a minimum-price flight route from Syrjala to Metsala. You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.

Example:

Input:  n = 3, m = 4, edges = {{1, 2, 3}, {2, 3, 1}, {1, 3, 7}, {2, 1, 5}}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const long long inf = 10000000000000000LL;

const long long N = 100005;
long long vis[N];
long long dis1[N], dis2[100005];

void dijkistrasAlgorithm(long long s, long long dis[],
                         vector<pair<long long, long long>> adj[])
{
    priority_queue<pair<long long, long long>> q;

    //initialize with very big number
    for (int i = 1; i < N; i++)
        dis[i] = inf;
    dis[s] = 0;
    q.push({0, s});

    //mark visited array as not visited
    memset(vis, 0, sizeof(vis));

    //iterate till the end of queue
    while (!q.empty())
    {

        long long a = q.top().second;

        //remove from the queue
        q.pop();

        //if already visited
        if (vis[a])
            continue;

        //mark as visited
        vis[a] = 1;
        for (auto edge : adj[a])
        {
            long long b = edge.first;
            long long w = edge.second;

            //relaxation
            if (dis[a] + w < dis[b])
            {
                dis[b] = dis[a] + w;
                q.push({-dis[b], b});
            }
        }
    }
}

long long flightDiscount(int n, int m,
                         vector<vector<long long>> &edges)
{

    vector<pair<long long, long long>> adj1[n + 1];
    vector<pair<long long, long long>> adj2[n + 1];

    for (long long i = 0; i < m; i++)
    {
        long long a = edges[i][0];
        long long b = edges[i][1];
        long long w = edges[i][2];

        adj1[a].push_back({b, w});
        adj2[b].push_back({a, w});
    }
    dijkistrasAlgorithm(1, dis1, adj1);
    dijkistrasAlgorithm(n, dis2, adj2);
    long long mn = inf;
    for (auto edge : edges)
    {
        long long a = edge[0];
        long long b = edge[1];
        long long w = edge[2];
        mn = min(mn, dis1[a] + dis2[b] + w / 2);
    }
    return mn;
}
int main()
{

    long long n = 3, m = 4;

    vector<vector<long long>> edges = {{1, 2, 3},
                                       {2, 3, 1},
                                       {1, 3, 7},
                                       {2, 1, 5}};

    cout << flightDiscount(n, m, edges) << "\n";

    return 0;
}