問題
既存投稿一覧ページへのリンク
解法手順1
問題の概要
- N個の都市があり、各都市iには観光スポットがA[i]個ある
- M本の道路があり、都市u,vを結ぶ道路の通行料はbである
- 都市1から各都市へ行く最小コストを求める問題
- コストは「通った道路の通行料 + 訪れた都市の観光スポット数」の合計
解法ステップ
ステップ1: 必要なデータ構造を準備する
# 各都市への最小コストを無限大で初期化
min_cost = [float('inf')] * N
# 優先度付きキューを準備（コスト, 都市番号）の形式
queue = [(A[0], 0)] # 最初は都市1（インデックス0）のコストA[0]から始める
heapq.heapify(queue)
このステップでは、各都市への最小コストを記録する配列と、探索するための優先度付きキューを準備する。
最初は都市1（インデックス0）から始め、その初期コストは都市1の観光スポット数Aである。
ステップ2: ダイクストラ法による最短経路探索
while queue:
now_cost, now = heapq.heappop(queue) # コストが最小の都市を取り出す
# すでに見つかっている経路の方がコストが小さい場合はスキップ
if min_cost[now] <= now_cost:
continue
# 現在の都市への最小コストを更新
min_cost[now] = now_cost
キューから最小コストの都市を取り出し、その都市への最小コストを更新する。
すでに見つかっている経路の方がコストが小さい場合は処理をスキップする。
ステップ3: 隣接都市の探索と更新
# 現在の都市から行ける全ての都市について処理
for next_node, road_cost in edges[now]:
# 次の都市へのコスト = 現在までのコスト + 道路の通行料 + 次の都市の観光スポット数
next_cost = now_cost + road_cost + A[next_node]
# より小さいコストで行ける場合のみキューに追加
if next_cost < min_cost[next_node]:
heapq.heappush(queue, (next_cost, next_node))
現在の都市から行ける全ての隣接都市について、新しいコストを計算する。
このコストが既知の最小コストより小さい場合、キューに追加して後で処理する。
ステップ4: 結果の出力
# 都市2以降（インデックス1以降）の最小コストを返す
return min_cost[1:]
全ての都市への最小コストが計算できたら、問題の要求通り都市2以降（インデックス1以降）の最小コストを返す。
ACコード1
ac.py
import heapq
import logging
def setup_logger(debug_mode):
logger = logging.getLogger(__name__)
if not logger.handlers: # ハンドラが存在しない場合のみ追加
logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
file_handler.setFormatter(formatter)
logger.addHandler(file_handler)
logger.debug("ロガーのセットアップが完了しました。デバッグモード: %s", debug_mode)
return logger
logger = setup_logger(False)
def io_func():
N, M = map(int, input().split())
A = list(map(int, input().split()))
edges = [[] for _ in range(N)]
for _ in range(M):
u, v, b = map(int, input().split())
edges[u - 1].append((v - 1, b))
edges[v - 1].append((u - 1, b))
return N, M, A, edges
def solve(N, M, A, edges):
logger.debug(f"都市の数: {N}, 道路の数: {M}")
logger.debug(f"各都市の観光スポット数: {A}")
logger.debug(f"道路の情報: {edges}")
min_cost = [float('inf')] * N
queue = [(A[0], 0)]
heapq.heapify(queue)
while queue:
now_cost, now = heapq.heappop(queue)
logger.debug(f"現在の都市: {now}, コスト: {now_cost}")
if min_cost[now] <= now_cost:
continue
min_cost[now] = now_cost
for next_node, road_cost in edges[now]:
next_cost = now_cost + road_cost + A[next_node]
logger.debug(f"次の都市: {next_node}, 次のコスト: {next_cost}")
if next_cost < min_cost[next_node]:
heapq.heappush(queue, (next_cost, next_node))
logger.debug(f"最小コスト: {min_cost[1:]}")
return min_cost[1:]
def main():
N, M, A, edges = io_func()
result = solve(N, M, A, edges)
print(*result)
if __name__ == "__main__":
main()
testcase-generatorによるテストケース生成(試行中)
testcase-generatorのclone
command
git clone https://github.com/naskya/testcase-generator.git
cd testcase-generator/
pip install -r requirements.txt
mkdir test_case
echo 'rm -f out.txt err.txt
rm -rf ./ac_input
mkdir ./ac_input
for file in ./test_case/*.txt; do
# 一時ファイルに標準エラー出力を保存
python3 test_code.py < "$file" >> temp_out.txt 2> temp_err.txt
# エラー出力があるかチェック
if [ -s temp_err.txt ]; then
# エラーがある場合
echo "=== エラー発生: $file ===" >> err.txt
cat temp_err.txt >> err.txt
echo "" >> err.txt # 空行を追加
else
# 正常終了の場合
echo "=== 正常終了: $file ===" >> out.txt
cat temp_out.txt >> out.txt
echo "" >> out.txt # 空行を追加
cp "$file" ./ac_input/
fi
# 一時ファイルを削除
rm -f temp_out.txt temp_err.txt
done' > test_bat.sh
chmod +x test_bat.sh
問題文にあったテストケースを作成
まだ本モジュールを使い始めたばかりなので練習として生成しています
fmt.txt
int N [7, 7]
int M [N - 1, 100]
row<int, N> A [3, 17]
graph<M, M> GMM connected no_multiple_edge no_self_loop
col<int, M> B [3, 13]
---
N M
A
GMM B
テストケースの生成
後でテストケースを確認するため、外部に保存
command
rm -rf test_case
mkdir test_case
python ./main.py gen -i fmt.txt -c 1000 -n -p test_case/ --suffix .txt
command
./test_bat.sh
正常データの抽出
command
rm -f program_trace.log
\cp -f ./test_case/0006.txt in.txt
python test_code.py < in.txt