C++ Modified Dijkstra : Worst case O(ElogV) time O(E + V) space
\tclass Solution {\n\tpublic:\n    int\n    minCost(int maxTime, vector>& edges, vector& passingFees) {\n        // Problem is modeled as an undirected graph wh
\tclass Solution {\n\tpublic:\n    int\n    minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        // Problem is modeled as an undirected graph wherein :-\n        // Cities are the graph vertices\n        // Bidirectional roads between cities are graph edges between vertices\n        // representing cities. Travel time between cities is the edge cost.\n        // The minimum journey between first city (0) and last city (n - 1)\n        // would be the shortest path between the two vertices based on the \n        // two parameters; total edge travel time not exceeding the maxTime\n        // and total passing time of all path vertices on the path being the\n        // minimum => modified Dijkstra with two constraints\n        return minCostViaModifiedDijkstra(maxTime, edges, passingFees);\n    }\n    \n\tprivate:\n    \n    // Models the edge between 2 graph vertices (i.e. road between cities)\n    typedef struct _EdgeInfo {\n        // Neighbour vertex\n        int nv;\n        // Edge cost\n        int cost;\n    } EdgeInfoT;\n    \n    int\n    minCostViaModifiedDijkstra(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        \n        // Construct graph\n        buildGraph(edges);\n        \n        // Modified Dijkstra operating on two constraints to find the shortest path\n        // betwen 0 and \'n - 1\' vertices\n        // 1. Commence from vertex 0 with path cost being passing fee of vertex\n        //    0 at time \'0\'. Add vertex 0 to priority queue (PQ)\n        // 2. Select a vertex from the PQ to processed. Vertex which can reached\n        //    with least edge travel time is prioritised over others stored as\n        //    this reduces the chance of travel time hitting maxTime leading to\n        //    journey termination. Tie breaker amongst vertices with same travel\n        //    time is by preferring the vertex with shortest path cost (sum of all\n        //    vertex passing times on the path)\n        // 3. Skip processing the selected vertex \'v\'; if the vertex was already\n        //    reached earlier via a journey path earlier with lesser total travel\n        //    time and lesser path cost\n        // 4. Update the total travel time and path cost for the selected vertex\n        //    with the new values\n        // 5. Explore all neighbour vertices of the selected vertex \'v\'\n        // 6. Neigbour vertices of \'v\' which can be reached within the max allowable\n        //    travel time are added to the PQ for processing in the subsequent\n        //    iterations\n        // 7. Go to step 2 as long as there is vertex in the PQ for processing\n        \n        // Vertex reachability information\n        typedef struct _VertexInfo {\n            // Vertex\n            int v;\n            // Total travel time to reach vertex \'v\' (sum of edge times)\n            // from start vertex \'0\'\n            long time;\n            // Total path cost to reach vertex \'v\' (sum of passing times\n            // of all vertices on the path) from start vertex \'0\'\n            long pathCost;\n        } VertexInfoT;\n        \n        typedef struct _VertexInfoCmpObj {\n            bool\n            operator()(const VertexInfoT& vi1, const VertexInfoT& vi2) {\n                // Prefer vertex with lower journey cost if the travel times\n                // are same; else prefer vertex with lesser travel time\n                if (vi1.time == vi2.time) {\n                    return vi1.pathCost > vi2.pathCost;\n                }\n                return vi1.time > vi2.time;\n            }\n        } VertexInfoCmpObj;\n        // Priority Queue of vertex reachability information\n        priority_queue<VertexInfoT, vector<VertexInfoT>, VertexInfoCmpObj> pq;\n        \n        int nVertices = passingFees.size();\n        // Tracks the minimum journey/path cost to each vertex from vertex 0\n        vector<long> minCostV(nVertices, numeric_limits<int>::max());\n        // Tracks the minimum travel time cost to each vertex from vertex 0\n        vector<long> minTimeV(nVertices, numeric_limits<int>::max());\n        \n        // Step 1. Start from vertex 0. Add to PQ\n        minCostV[0] = 0;\n        VertexInfoT vi;\n        vi.v = 0;\n        vi.time = 0;\n        vi.pathCost = passingFees[0];\n        pq.push(vi);\n        \n        while (!pq.empty()) {\n            // Step 2. Select and dequeue the vertex at front of PQ\n            auto reachableVertexInfo = pq.top();\n            pq.pop();\n            // Selected vertex params\n            auto v = reachableVertexInfo.v;\n            auto time = reachableVertexInfo.time;\n            auto pCost = reachableVertexInfo.pathCost;\n            \n            // Step 3. Selected vertex was reachable from vertex \'0\' via a \n            // path with lesser/same travel time and path cost. So no sense\n            // in processing the vertex this time\n            if ((time >= minTimeV[v]) &&\n                (pCost >= minCostV[v]))  {\n                continue;\n            }\n            \n            // Step 4. Update total travel time and path cost to reach\n            // selected vertex as per new reacahbility info\n            minCostV[v] = min(minCostV[v], pCost);\n            minTimeV[v] = min(minTimeV[v], time);\n            \n            // Step 5. Iterate over each neighbor of selected vertex\n            auto & nbrInfoV = _adjList[v];\n            for (auto & nbrInfo : nbrInfoV) {\n                auto edgeCost = nbrInfo.cost;\n                auto nv = nbrInfo.nv;\n                if (edgeCost + time <= maxTime) {\n                    // Neighbour reachable from vertex from vertex \'0\' within\n                    // the max allowable travel time. Enqueue vertex to PQ\n                    // for further processing\n                    VertexInfoT nvInfo;\n                    nvInfo.v = nv;\n                    // Update the travel time and path cost  to neighbpur \'nv\'\n                    // via last hop as current select vertex\n                    nvInfo.time = edgeCost + time;\n                    nvInfo.pathCost = pCost + passingFees[nv];\n                    pq.push(nvInfo);\n                }\n            }\n        }\n        \n        \n        int minCostToDest = minCostV[nVertices - 1];\n        return (minCostToDest == numeric_limits<int>::max()) ? -1 : minCostToDest;\n    }\n    \n    void\n    buildGraph(vector<vector<int>>& edges) {\n        // Iterate over each edge of the graph\n        for (auto & edge : edges) {\n            // Edge vertices and cost\n            auto u = edge[0];\n            auto v = edge[1];\n            auto cost = edge[2];\n            // Bidirectional edge - add both (u, v) and (v, u) to\n            // graph adjacency list\n            EdgeInfoT e;\n            e.cost = cost;\n            e.nv = v;\n            _adjList[u].emplace_back(e);\n            e.nv = u;\n            _adjList[v].emplace_back(e);\n        }\n    }\n    \n    // Data members\n    \n    // Graph Adjacency list representation. Maps each vertex to list of\n    // edges incident on the vertex. Edge information consists of neighbour\n    // vertex and edge cost tuples\n    unordered_map<int, vector<EdgeInfoT> > _adjList;\n\t};
['Heap (Priority Queue)']