C++ Solution || DP with Dijkstra || Easy to understand
Below solution combines DP with Dijkstra\'s algorithm to achive the min cost possible. Do comment if anything is not clear.\n\n```\ntypedef pair> pii;\n\nclass 
Below solution combines DP with Dijkstra\'s algorithm to achive the min cost possible. Do comment if anything is not clear.\n\n```\ntypedef pair<int,pair<int,int>> pii;\n\nclass Solution {\npublic:\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        int n=passingFees.size();\n\n\t//state of dp(i,j) : stores the min cost to reach city \'i\' in \'j\' max time;\n    int dp[n][maxTime+1];\n      \n\t\t\n\t\t//without using another array for time will result in TLE since it will explore more paths, hence \n\t\t//using another array that stores the min time the city was discovered. This improves the TC to a \n\t\t//huge extent as it prunes some path.\n\t\t\n        int ttime[n];\n        for(int i=0;i<n;i++){\n            ttime[i]=INT_MAX;\n            for(int j=0;j<=maxTime;j++){\n                dp[i][j]=INT_MAX;\n            }\n        }\n        ttime[0]=0;\n        dp[0][0]=passingFees[0];\n        \n        vector<vector<int>>adj[n];\n        for(auto x:edges){\n            adj[x[0]].push_back({x[1],x[2]});\n            adj[x[1]].push_back({x[0],x[2]});\n        }\n        \n\t\t// first priority is to minimise the cost associated with the path, {cost, city, time}\n        priority_queue<pii,vector<pii>,greater<pii>>minHeap;\n        minHeap.push({passingFees[0],{0,0}});\n        \n        while(!minHeap.empty()){\n            auto top=minHeap.top();\n            minHeap.pop();\n           \n\t\t   int u=top.second.first; \n            int time=top.second.second;\n            int cost=top.first;\n\n\t\t\tif(u==n-1)return cost;\n\n\t\t\tttime[u]=time;\n            \n            for(auto x:adj[u]){\n\t\t\t// this is the pruning part, where we are only exploring paths that can be reached earlier than \n\t\t\t//the time already required.\n                if(time+x[1]<ttime[x[0]]){\n                    if(time+x[1]<=maxTime){\n\t\t\t\t\t//now we are checking if the cost to reach the neighbor is less than the already minimum \n\t\t\t\t\t//cost, denoted by dp[x[0]][time+x[1]], denoting min cost to reach x[0] in \'time+x[1]\' max \n\t\t\t\t\t//time.\n                        if(cost+passingFees[x[0]]<dp[x[0]][time+x[1]] ){\n                            dp[x[0]][time+x[1]]=cost+passingFees[x[0]];\n                            ttime[x[0]]=time+x[1];\n                            minHeap.push({dp[x[0]][time+x[1]],{x[0],time+x[1]}});\n                        }\n                    }\n                }\n            }\n        }\n        return -1;\n    }\n};\n
['Dynamic Programming', 'C', 'Heap (Priority Queue)']