java - 寻找等待时间最短的路径

Question

我正在通过竞赛解决这个问题。我将在这里简要描述问题。

一位厨师试图在时间 T 之前到达 session 地点，但他希望在公共(public)汽车站的等待时间最短。他不介意走很远的路，除非他在 T 之前到达目的地并且在公共(public)汽车站等的时间最少。他从第 1 站出发，目的地是最后一站。这是输入规范......

N T M 
U V S E
U V S E
... and so on

其中 N 是车站的数量，T 是集合时间，M 是公交车的数量。接下来的 M 行是公交车的详细信息。 U 是公共(public)汽车的起点，V 是它到达的地方。 S是开始时间，E是到达时间。所以一辆公共(public)汽车在时间 S 从车站 U 出发，在时间 E 到达车站 V。

Constraints
2 ≤ N ≤ 50000
1 ≤ T ≤ 109
1 ≤ M ≤ 100000 (105)
1 ≤ U ≤ N
1 ≤ V ≤ N
U ≠ V
0 ≤ S < E ≤ 10

这是我尝试过的，解释在代码之后和代码中。

public int findMax(int nextStation, int rcd, int start, int end) {
    int tt = start - rcd;
    // If we reached destinaion, i.e the last station
    // no more wait has to be done and we return the time
    // required to reach here
    if (nextStation == noOfStations) {
        return tt;
    }

    // TODO : we already found a better path, so we skip this one
    // if (tt > minTillNow) {
    // return Integer.MAX_VALUE;
    // }

    List<Bus> buses = stations.get(nextStation);

    // If we have not reached finalStation
    // and there are no more buses from this station,
    // we reached a dead end.
    if (buses == null) {
        return -1;
    }

    int temp, min = Integer.MAX_VALUE;
    // If there are buses from this station, we try all
    // of them
    for (int i = 0; i < buses.size(); i++) {
        temp = findMax(buses.get(i).v, end, buses.get(i).s, buses.get(i).e);
        // Find minimum wait-time
        if (temp != -1 && temp < min) {
            min = temp;
        }
    }
    // If no subtree has a path
    if (min == Integer.MAX_VALUE) return -1;
    // if the wait to reach here is greater than any subsequent
    else if (min < tt) return tt;
    else
        return min;
}

我正在做一个 DFS，从第一个站开始，找到沿着任何路径直到结束的最大等待时间，然后选择沿着这些路径的所有等待时间的最小值。这适用于给定的输入示例..

Input:
5 10 5
1 2 1 2
1 5 3 4
2 4 4 5
2 5 5 6
4 5 6 7

Output:
2 

但是当我提交它进行一些测试输入时失败，并显示“错误答案”。 有人能发现上述方法的问题吗？一般来说，这也是一个好方法吗？这会有什么复杂性？我认为它在 M 中应该是线性的，是正确的近似值。

Answer 1

我想你忘记的是测试你是否仍然可以在 for 循环中 catch 公共(public)汽车(如下面的示例所示)。

除此之外，我认为您的代码比需要的更复杂。一方面，用-1编码'no path'不是很方便，因为在评估最小等待时间时需要额外测试(我假设你必须返回-1如果没有路径，但你最后可以处理)。

我会提出以下功能(并为 N 和 T 引入新名称，但我认为它们足够有意义)。

public int minWaitingTime(int currentStop, int currentTime, int waitingTime) {
    if (currentStop == destination) {
        // reached the destination, return waitingTime if we met the deadline, 
        // or 'infinity' otherwise
        // NOTE: I assumed currentTime <= deadline is ok, maybe that should be <
        return currentTime <= deadline ? waitingTime : Integer.MAX_VALUE;
    } else {        
        List<Bus> buses = stations.get(currentStop);

        int min = Integer.MAX_VALUE;
        for (Bus bus : buses) {
            // test if we can still catch this bus
            if (bus.s <= currentTime) {
                // update minimum
                min = Math.min(min, 
                        minWaitingTime(bus.v, bus.e, 
                            waitingTime + (bus.s - currentTime));
            }
        }

        return min;
    }
}

您现在可以将其称为:

public int findMinWaitingTime() {
    int min = minWaitingTime(1, 0, 0);
    return min == Integer.MAX_VALUE ? -1 : min;
}

顺便说一句，我希望这是一个老比赛，我现在不是在写你的解决方案......