14weblabAD

package weblab;

import nl.tudelft.weblab.runner.*;
import java.io.*;
import java.util.*;

/**
 * WARNING: The spec tests are not necessarily equal to your grade! You can use them help you test
 * for the correctness of your algorithm, but the final grade is determined by a manual inspection
 * of your implementation.
 */
class TheQuestForTheHolyGrail {

    /**
     * You should implement this method.
     *
     * @param n the number of nodes.
     * @param m the number of edges.
     * @param k the number of times we can use the research team
     * @param g the index of the holy grail in V.
     * @param V a list of Nodes, where V[1] is the current state and V[g] is the holy grail. You
     *     should not use V[0].
     * @param E a set of Edges
     * @return The length of the shortest path that uses the research team at most k times.
     */
    public static double solve(int n, int m, int k, int g, Node[] V, Set<Edge> E) {

        double[][] dp = new double[n + 1][k + 1];
        for (int node = 1; node <= n; ++node)
          for (int j = 0; j <= k; ++j)
            dp[node][j] = Double.MAX_VALUE / 2;

        for (int j = 0; j <= k; ++j)
          dp[1][j] = 0;


        for (int it = 0; it < n - 1; ++it) // at most "n-1" times repeat the process, so that the distances can succesfully propagate in Graph
        {
          for (int node = 1; node <= n; ++node) {
            for (Edge e: E)
              if (e.to.getId() == node) {
                int from = e.from.getId();
                int to = e.to.getId();
                int cost = e.cost;

                dp[to][0] = Math.min(dp[to][0], dp[from][0] + cost);
                for (int j = 1; j <= k; ++j)
                  dp[to][j] = Math.min(dp[to][j], Math.min(dp[from][j] + cost, dp[from][j-1] + cost * 0.5));

              }

          }
      }

      if (dp[g][k] == Double.MAX_VALUE / 2)
        return -1;
      else
        return dp[g][k];
  }
}

class Node {

    protected int id;

    public Node(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public boolean equals(Object other) {
        if (other instanceof Node) {
            Node that = (Node) other;
            return this.id == that.id;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

class Edge {

    protected int cost;

    protected Node from;

    protected Node to;

    protected Edge(Node from, Node to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }

    public Node getFrom() {
        return from;
    }

    public Node getTo() {
        return to;
    }

    public int getCost() {
        return cost;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Edge edge = (Edge) o;
        return cost == edge.cost && Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
    }

    @Override
    public int hashCode() {
        return Objects.hash(cost, from, to);
    }
}