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 は到達時刻です。バスは駅 U を時刻 S に出発し、時刻 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 の問題のようです。他の人が作成したソリューションは、Web サイトで見つけることができます。

深さ優先検索を使用する際の問題は、幾何学的に複雑さが増すことです。たとえば、10 のステーションがあり、各ステーションから 10 の接続がある場合、10 の 10 乗のパスがあり、これは数十億になります。力ずくでチェスを解こうとするようなものです。

この種の問題は動的計画法で解決できます (Code Jam は DP 問題が大好きです)。これを知っている理由は、特定の駅での最善の移動は、以前に行った駅とは無関係だからです。問題を解決するには、最後のステーションから逆方向に作業します。この方法で、特定の動きの最小待ち時間をいつでも見つけることができます。

唯一の問題は、最小待ち時間パスが T の後に到着する可能性があることです。

したがって、この問題を解決するには、最小待機パスでバックトラッキング検索を実行する必要があります。つまり、以前と同じように DP ソリューションを実行しますが、費やされた合計時間を追跡します。T を超える場合は、前のノードに戻り、そこから検索を続けます。

ところで、「temp」や「i」などの無意味な変数名の使用は避けてください。間違いにつながります。

于 2013-05-07T19:30:03.360 に答える