1

http://codility.com/には、次のような問題があります。

あなたの近所には N 個の正方形があり、それらを結ぶ M 本の直通道路があります。正方形には 0 から N − 1 までの番号が付けられています。あなたは正方形 0 に住んでおり、0 秒で到達できます。店舗は、それぞれの広場に 1 つずつ配置されています。4 つのゼロ インデックス配列 A、B、C、および D の形式で近隣のマップが与えられます。配列 A、B、C のそれぞれには M 個の整数が含まれ、D には N 個の整数が含まれます。各 I (0 ≤ I < M) について、正方形 A[I] と B[I] の間の歩行距離は C[I] 秒です (どちらの方向にも)。

同じ正方形のペアを接続する複数の道路、または両端が同じ正方形に入る道路が存在する可能性があります。

一部の道路がトンネルを通過したり、橋を渡ったりする可能性があります (つまり、正方形と道路のグラフは平面である必要はありません)。

すべてのマスに到達できるとは限りません。各 J (0 ≤ J < N) に対して、正方形 J の店は D[J] 秒で閉店します (D[J] = −1 の場合、店は既に閉店しています)。閉店ギリギリに着いても購入可能です。関数を書く:

int solution(int A[], int M, int B[], int M2, int C[], int M3, int D[], int N);

配列 A、B、C、D を指定すると、開いている店舗に到達するのに必要な最小時間 (秒単位) が返されます。不可能な場合は、-1 を返す必要があります。

私の主な問題は、問題を特定することです。私は数学に深いバックグラウンドを持っていません。私はテストを行い、サンプルデータが質問で提供するように機能しますが、送信後、ウェブサイトはこのデータが間違っていると言っていますdata = [[6, 6, 3, 8, 8, 6, 7, 5, 1, 4, 3, 2, 7, 7], [3, 7, 5, 8, 0, 6, 3, 4, 1, 7, 1, 5, 3, 2], [8, 1, 9, 12, 11, 1, 8, 12, 3, 6, 12, 7, 4, 2], [-1, 1000000000, 1000000000, 999999999, 999999999, 999999999, 1000000000, 1000000000, 1000000000]]

-1 を返しますが、11 を返す必要があると表示されます。0 (自宅) から開始して、より近い店舗を見つけようとすると、0 は 8 に接続し、8 はどこにも接続されないため、行き詰まります。グラフを描画し、0 ～ 8 を残りから切り離します。http://en.wikipedia.org/wiki/Bridge_(graph_theory)に関連していると思われますが、ここで私の知識が止まります。

これは問題の適切な識別ですか?

PD: Python コードの問題を理解することにもっと興味があります。

4

1 に答える 1

0

いくつかのアプローチを大まかに説明します。うまくいけば、いくつかのアイデアが得られるでしょう。自分で解決できれば、問題解決能力が向上するようです。

アプローチ 1.

二分探索を使用して最小時間を計算します。二分探索の推測ごとに、その時間内に店舗に到達できるかどうかを判断する関数を用意します。(可能であれば時間を減らし、そうでない場合は増やしてください)。可能かどうかは、幅優先検索の深さ優先検索 (推測よりも離れたノードで停止) で確認できます。

アプローチ 2。

pythons heapq データ構造を使用します。[(0, start)] の初期ヒープから開始します。0 は距離 0、start は開始ノードです。次に、開始点に接続されたノード x ごとに、heapq (dx は開始点から x までの距離) に heappush (0 + dx, x) します。今スタートをポップします。次に最適なノードをポップします。距離が D[x] 未満かどうかを確認します。継続する。

于 2013-05-25T06:21:30.567 に答える