1

我正在从比赛中解决这个问题。我将在这里简要描述问题。

一位厨师试图在时间 T 之前参加会议，但他希望在公交车站等待时间最短。他不介意走很长的路，除非他在 T 之前到达目的地并且在公共汽车站等的时间最少。他从 1 号站开始，目的地是最后一站。这是输入规范...

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

其中 N 是车站数量，T 是集合时间，M 是公共汽车数量。接下来的 M 行是巴士详情。U 是公共汽车的起点，V 是它到达的地方。S是开始时间，E是到达时间。因此，一辆公共汽车在时间 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 中应该是线性的，是正确的近似值。

4

2 回答 2

1

这看起来像是一个 Google Code Jam 问题。您可以在他们的网站上找到其他人提出的解决方案。

使用深度优先搜索的问题在于它具有几何增加的复杂性。因此，例如，如果您有 10 个站点和每个站点的 10 个连接，则您有 10^10 条路径，以十亿计。这就像试图用蛮力解决国际象棋。

这种问题可以用动态规划来解决（Code Jam 喜欢 DP 问题）。您知道这一点的原因是，任何给定车站的最佳移动与您之前去过的车站无关。为了解决这个问题，从最后一站向后工作。通过这种方式，您将始终能够找到任何特定移动的最短等待时间。

唯一的障碍是最短等待时间路径可能在 T 之后到达。

因此，为了解决这个问题，您应该对最小等待路径进行回溯搜索。换句话说，您像以前一样执行 DP 解决方案，但要跟踪花费了多少总时间。如果超过 T，则回溯到前一个节点并从那里继续搜索。

顺便说一句，避免使用无意义的变量名，如“temp”和“i”，这会导致错误。

于 2013-05-07T19:30:03.360 回答
1

I think what you're forgetting is to test whether you can still catch the bus in the for loop (as shown in my example below).

Apart from that, I think your code is more complicated than needed. For one, it is not very convenient to encode 'no path' by -1, because that requires extra testing when evaluating the minimum waiting time (I assume you have to return -1 if there is no path, but you can deal with that in the end).

I would propose the following function (and introduced new names for N and T, but I think they are meaningful enough).

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;
    }
}

You could now just call this as:

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

Btw, I hope this is an old competition and I'm not writing your solution now...

于 2013-05-07T19:04:36.833 回答