CareerCup

/**
     * The algorithm takes O(k) space (for PriorityQueue and HashMap).
     * The runtime is (O (k) + O((n - k) log k) to build up the heap and O(n) to iterate through the length of the matrix.
     */
    public int findShortestPath(@Nonnull int[][] matrix, int k) {
        if (matrix.length == 0 || matrix[0].length == 0 || matrix[0].length != matrix.length) {
            return -1;
        }
        PriorityQueue<Integer> minHeapForMaxDistance = new PriorityQueue<>(k);

        int currentDistance = 0;
        // determine the longest distances that will be skipped later. The longest distance will be added
        // into the min heap. If the current distance is > then the min, it will be replaced.
        // This takes (O (k) + O((n - k) log k)
        for (int i = 1; i < matrix.length; ++i) {
            currentDistance = matrix[i - 1][i];
            while (minHeapForMaxDistance.size() >= k &&
                    minHeapForMaxDistance.peek() < currentDistance) {
                minHeapForMaxDistance.poll();
            }

            if (minHeapForMaxDistance.size() < k) {
                minHeapForMaxDistance.offer(currentDistance);
            }
        }

        int shortestPath = 0;
        // after we found all max distances, we put them into a HashMap. The key is the max distance and the value the
        // amount of max distances in the matrix. s represents source, t represents target position.
        Map<Integer, Integer> maxDistances = from(minHeapForMaxDistance);
        for (int s = 0, t = 1; t < matrix.length; ++t) {
            currentDistance = matrix[s][t];

            // found a max distance. Skip it. e.g. the path from a-800->b-300->c and a-400->c. B will be skipped
            // and a->c will be used.
            if (maxDistances.containsKey(currentDistance) &&
                    maxDistances.get(currentDistance) > 0) {
                maxDistances.put(currentDistance, maxDistances.get(currentDistance) - 1);
            } else {
                shortestPath += currentDistance;
                s = t;
            }
        }
        return shortestPath;
    }


    /**
     * Converts the priority queue to the HashMap. The key is the distance, the value the amount of the distance.
     */
    private Map<Integer, Integer> from(PriorityQueue<Integer> minHeapForMaxDistances) {
        Map<Integer, Integer> maxDistances = new HashMap<>();

        int current;
        while (!minHeapForMaxDistances.isEmpty()) {
            current = minHeapForMaxDistances.poll();
            if (maxDistances.containsKey(current)) {
                maxDistances.put(current, maxDistances.get(current) + 1);
            } else {
                maxDistances.put(current, 1);
            }
        }
        return maxDistances;
    }

EDIT: On second thought this approach might not work in case we have the same max distance more then k times. Then there is a difference how we follow the path

Top down dynamic programming. O(n^2 * k) time and O(n^3 * k) space.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Path {
	public:
		Path()
		{
			distance_ = 0;
		}
		vector<int> cities_;
		int distance_;
};

Path ShortestPath(int n, vector<vector<int>> const &distances, unordered_map<uint64_t, Path> &memo,
	int k, int16_t idx = 0, int16_t prev_idx = -1)
{
	if (idx < 0 ||
		idx >= n)
	{
		return Path();
	}

	uint64_t memo_key = (static_cast<uint64_t>(k) << 32) | (static_cast<uint32_t>(idx) << 16) | prev_idx;
	auto it = memo.find(memo_key);
	if (it != memo.end()) {
		return it->second;
	}

	Path path = ShortestPath(n, distances, memo, k, idx + 1, idx);
	path.cities_.push_back(idx);
	if (prev_idx != -1) {
		path.distance_ += distances[prev_idx][idx];
	}
	if (k > 0) {
		Path skip = ShortestPath(n, distances, memo, k - 1, idx + 1, prev_idx);
		if (skip.distance_ < path.distance_) {
			path = skip;
		}
	}

	memo[memo_key] = path;
	return path;
}

int main()
{
	int n = 5;
	int k = 2;

	vector<vector<int>> distances(n, vector<int>(n, numeric_limits<int>::max()));
	distances[0][1] = 2;
	distances[0][2] = 9;
	distances[0][3] = 7;
	distances[0][4] = 5;
	distances[1][2] = 7;
	distances[1][3] = 1;
	distances[1][4] = 5;
	distances[2][3] = 1;
	distances[2][4] = 8;
	distances[3][4] = 1;

	unordered_map<uint64_t, Path> memo;
	Path path = ShortestPath(n, distances, memo, k);

	cout << path.distance_ << ": ";
	for (int i = path.cities_.size() - 1; i >= 0; --i) {
		cout << path.cities_[i] << "->";
	}
	cout << "\n";
}