【連結の判定】STEP: 4 重みあり有向グラフの隣接行列と隣接リスト (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【連結の判定】STEP: 4 重みあり有向グラフの隣接行列と隣接リスト (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
前回と同じく隣接行列と隣接リストを出力します。今回違うのは有向グラフという向きと重みを記録するところです。っといっても向きの記録は隣接行列、隣接リスト共に例えば「頂点1⇒頂点4に向き」があれば「隣接行列[1][4]だけに重み、隣接リストの1行目に4（重み）」という感じで記録していきます。記録の仕方が少し違うのと、今まで隣接行列に「1」、隣接リストに頂点番号を記録していましたが、そこが重みに変わっただけと考えればそれほど難しくないですね(*’ω’*)
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; //頂点の数 $m = $input[1]; //辺の数 for($i = 0;$i < $n;$i++){ for($j = 0;$j < $n;$j++){ $a_array[$i][$j] = 0; // 隣接行列の配列を作成 $b_array[$i] = array(); // 隣接リストの配列を作成 } } for($i = 0;$i < $m;$i++){ $test = explode(" ",trim(fgets(STDIN))); $a = $test[0] - 1; $b = $test[1] - 1; $k = $test[2]; //重み $a_array[$a][$b] = $k; // 隣接行列を作成 $b_array[$a][$b] = "(".$k.")"; // 隣接リストの作成 } foreach($a_array as $value1){ // 隣接行列を出力 foreach($value1 as $value2){ echo $value2; } echo "\n"; } foreach($b_array as $value1){ // 隣接リストを出力 ksort($value1); foreach($value1 as $key => $value2){ echo $key.$value2; } echo "\n"; } ?> |
