プログラミングコンテストの質問をしたところ、完全に爆撃しました。入力セットの読み取りから、最初の段階で問題が発生しました。質問は基本的にこのパズルhttp://codercharts.com/puzzle/evacuation-planの変形ですが、最初の行に時間要素もありました (たとえば、避難開始から 3 時間後)。このように読みます
このパズルは、日本の地震で苦しんだすべての人々へのオマージュです。このパズルの目標は、道路と場所のネットワークを考慮して、避難できる最大人数を決定することです。
人々は避難場所から救助場所に避難しなければなりません。道路のリストと、1 時間あたりに運べる人数が表示されます。
入力仕様 プログラムは、1 つのコマンド ライン引数 (入力ファイル) のみを受け入れる必要があります。入力ファイルは次のようにフォーマットされます: 最初の行には 4 つの整数が含まれます nrstn は場所の数です (各場所は 0 から n-1 までの数字で指定されます) r は道路の数です s は避難する場所の数ですfrom (避難場所) t は、人々が避難しなければならない場所 (救助場所) の数です。2 行目には、避難場所の場所を示す整数 s が含まれます。3 行目は、救助場所の場所を示す整数 t が含まれます。次の r行には、道路の定義が含まれています。各道路は 3 つの整数 l1 l2 幅で定義されます。ここで、l1 と l2 は道路で接続された場所 (道路は一方通行) で、幅は道路に収まる 1 時間あたりの人数です。
次に、サンプル入力セットを見てください
5 5 1 2 3
0
3 4
0 1 10
0 2 5
1 2 4
1 3 5
2 4 10
最初の行の 3 は追加のコンポーネントであり、再開が開始されてからの時間数として定義されます。この場合は 3 です。
私の解決策は、Dijisktras アルゴリズムを使用して、レスキュー ノードと避難ノードのそれぞれの間の最短経路を見つけることでした。今、私の問題は、入力セットを読み取る方法から始まりました。Python で最初の行を読み取り、値を変数に格納しました。しかし、その後、ノード間の距離の値を保存する方法と、どの DS を使用するか、それを入力して dijikstras アルゴリズムの標準実装と言う方法がわかりませんでした。
したがって、私の質問は 2 つあります。-最近、かなりの数の競技会でこの問題に直面しました。JavaまたはPythonで簡単なコードスニペットまたは説明を取得して、データ入力セットを読み取り、グラフとして入力してアルゴリズムをグラフ化できることを願っていますダイクストラとフロイド/ウォーシャルのように。また、上記の問題の解決策も役立ちます。
2.) このパズルの解き方は？私のアルゴリズムは次のとおりです。
- 避難ポイント間の最短経路を見つけます (上記の例では、0 から 3 までの 14 です)。
- 保存の最大数を取得するには、時間数を掛けます
また、入力セットのバリアントに対する回答は 24 でしたが、これはわかりません。誰かがそれも説明できますか。
アップデート：
与えられた問題のリンクで答えが 14 であることがわかります - ノード 0 と 3 の間の最短経路のようです。しかし、3 時間のコンポーネントでは、答えは 24 です
アップデート
私はそれが24であることを理解しています-それは毎時間の完全なグラフトラバーサルであり、これが私がそれを解決する方法です
Hour 1
Node 0 to Node 1 - 10 people
Node 0 to Node 2- 5 people
TotalRescueCount=0
Node 1=10
Node 2= 5
Hour 2
Node 1 to Node 3 = 5(Rescued)
Node 2 to Node 4 = 5(Rescued)
Node 0 to Node 1 = 10
Node 0 to Node 2 = 5
Node 1 to Node 2 = 4
TotalRescueCount = 10
Node 1 = 10
Node 2= 5+4 = 9
Hour 3
Node 1 to Node 3 = 5(Rescued)
Node 2 to Node 4 = 5+4 = 9(Rescued)
TotalRescueCount = 9+5+10 = 24
この場合、複数の evac およびレスキュー ポイントの場合、このための pgm をどのように作成すればよいのでしょうか。