Minimum Penalty Path Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Minimum Penalty Path
  5. Discussions

Minimum Penalty Path

  • junkmann
     + 1 comment

    It can be solved pretty easily by using brute force since the maximum edge cost is pretty small (1023).

    The key observation to make is that the answer lies between 1 and 1023, if there is a path from A to B, otherwise -1. So you can just test if it's possible to get from A to B with a cost of 1, 2, 3, ... up to 1023. So all that is left is to create a graph where the OR of all its edges results to the cost you are testing for.

    public static int beautifulPath(List<List<int>> edges, int A, int B)
{
	--A;
	--B;

	var edgesGroupedByCost = new List<(int U, int V)>[1024];

	for (var c = 0; c < 1024; ++c) {
		edgesGroupedByCost[c] = new();
	}

	foreach (var edge in edges) {
		var u = edge[0] - 1;
		var v = edge[1] - 1;
		var c = edge[2];

		edgesGroupedByCost[c].Add((u, v));
	}

	var ds = new DS(1000);

	for (var r = 1; r < 1024; ++r) {
		ds.Clear();

		for (var c = 1; c < 1024; ++c) {
			if ((r | c) == r) {
				foreach (var (u, v) in edgesGroupedByCost[c]) {
					ds.Union(u, v);
				}
			}
		}

		if (ds.Find(A) == ds.Find(B)) {
			return r;
		}
	}

	return -1;
}

    I used a disjoinct set data structure to see if A and B are connected in the resulting graph but I'm pretty sure just doing a DFS from A to see if you can reach B works too.