Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1359-089d9665
この記事にトラックバックする(FC2ブログユーザー)

UVa 11812 - Innovative Procession Management (この記事を編集する[管理者用])

Source

A Contest from BUBT, Bangladesh (2010-06-27) (blog)
UVa 11812

問題概要

ノード数100以下,枝数10000以下の有向グラフが与えられる.枝には距離がある.
始点の集合と終点(1個)が与えられたとき,最短パスがある限り,その最短パスのどれかに含まれている枝を取り除くという作業を行う.
その過程において,最短パスの長さと,そのとき取り除かれた枝を全部出力する問題.

解法

毎回ダイクストラして,シミュレーションする.
最悪ケースだとO(m^2)なのだけど,あんまり計算時間の大きくなるケースはないみたいで,十分間に合う.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1359-089d9665
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。