2024-12-24から1日間の記事一覧
AOJ
AOJ-ICPC
ICPCアジア
考察:主客転倒・寄与分解
グラフ
【問題集】最短路問題
最短路問題
最小全域木
最小コスト
Dijkstra法
式変形
式変形テク:シグマの入れ替え
考察:操作・条件・目的関数を言い換える
面白かった! 一見 MST の問題に見えるけど、主客転倒すると Dijkstra だった。 問題へのリンク(仮) 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。頂点 には重み がついていて、辺 には重み がついている。このグラフの全域木のコストを次…