Editorialist: wes

This problem was a single-destination shortest path (SDSP) problem: given a graph (a set of nodes connected by edges) and a destination node, find the length of the shortest path through the graph from every source node to the destination. In this case, the planets are the nodes and the wormholes are directed edges with weights equal to the time travelled through the wormhole. All you need to do is the count the number of source nodes (excluding the destination) that have a path to the destination less than or equal to \(-M\). From the problem description we know that every source is guaranteed a path to the destination, there are no negative weight cycles in the graph, and there are no self-loops.

Given that the graph contains negative edge weights, suitable algorithms are Bellman-Ford or Floyd-Warshall, which would solve the problem for all sub-problems. Bellman-Ford is a single-source shortest path (SSSP) algorithm, so would require reversing the edge directions to convert the SDSP into an SSSP. Floyd-Warshall is an all-pairs shortest path algorithm, and easier to implement given that the main part of the algorithm is only 4 lines. In this case, both algorithms have time complexity \(O(P^3)\).

The bounds on the first sub-problem (\(N = P-1\)), combined with the fact that every source is guaranteed a path to the destination, tell you that the shape of the graph forms a tree and every source has exactly one path to the destination, thus any search algorithm would work. The second sub-problem is the same as the third but with only positive edge weights, thus Dijkstra's algorithm would also work but it would fail on the third sub-problem due to the negative edge weights.

Given that each case can have up to \(10^4\) lines of input, using fast I/O might be a good idea.

An example solution in Java using Floyd-Warshall follows:

Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
int numCases = in.nextInt();
for (int c=0; c<numCases; c++) {
    int numE = in.nextInt();
    int threshold = -in.nextInt();
    int numV = in.nextInt();
    boolean[][] connected = new boolean[numV][numV];
    int[][] edgeWeight = new int[numV][numV];
    for (int i=0; i<numE; i++) {
        int s = in.nextInt();
        int e = in.nextInt();
        int w = in.nextInt();
        connected[s][e] = true;
        edgeWeight[s][e] = w;
    }
    for (int i=0; i<numV; i++)
        connected[i][i] = true;
    long[][] dist = new long[numV][numV];
    for (int i=0; i<numV; i++)
        for (int j=0; j<numV; j++)
            dist[i][j] = (connected[i][j] ? edgeWeight[i][j] : 1000001);
    for (int k=0; k<numV; k++)
        for (int i=0; i<numV; i++)
            for (int j=0; j<numV; j++)
                dist[i][j] = Math.min(dist[i][j],dist[i][k] + dist[k][j]);
    int count = 0;
    for (int i=1; i<numV; i++)
        if (dist[i][0] <= threshold)
            count++;
    System.out.printf("%d\n",count);
}