Competitive Programming Editorials

  Problem Link Time Complexity: O(N + M log M) Algorithm used: Dijkstra, DP (partly) The problem statement is quite straightforward: a series of M one-way flight routes are described, each connecting one city to another city and having a cost. You want to travel from city 1 to city N. Find: minimum price of such a route the number of minimum-price routes maximum number of flights in a minimum-price route minimum number of flights in a maximum-price route It is guaranteed that at least 1 path exists from city 1 to city N This can be modelled as a graph problem, where the cities are the nodes and the flights are the edges. Each flight has a cost and only travels in one direction, so the graph is weighted and directed. A minimum price route to node N means the shortest path to node N. Since the route must start from city 1 and the edges are weighted, some form of Dijkstra's algorithm must be applied. The key point is to collect the data for the 4 answers while running the Dijkstra...

  Problem Link Time Complexity: O(Nlog(KlogK)) Algorithm used: Dijkstra's algorithm, Binary Search This  is where I understood how to solve this problem in time. In this problem, the breeds of N cows are given, followed by a K by K matrix, describing whether or not a cow of breed i is willing to transmit a message to cow of breed j. The cost of sending a message from cow i to cow j is |i - j|. Find the minimum possible cost of transmitting a message from cow 1 to cow N. This problem can be represented as a graph problem, where the cows are the nodes and edges are drawn between the nodes depending on the compatibility of cow breeds, described in the matrix. While reading in the matrix, also create an adjacency list for every breed. Intuitively, we could run a standard  Dijkstra's algorithm  starting from cow 1 and loop over the adjacency list for every pass of the algorithm. Although this implementation would always produce the correct answer, the program would exceed...