ダイクストラ法
問題 日本語なので本文参照(http://kupc2014.contest.atcoder.jp/tasks/kupc2014_h)
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp) 制約条件 h, w≦30
問題 n個の路線がある。 i番目の路線はai個の駅をつなぎ、 それぞれの駅名および、j番目とj+1番目の駅の所要時間が与えられる。 今sの駅からtの駅へ、路線を使っていきたい。 電車はどちらの向きにも使うことができるが、乗り換えには1回あたりTの時間がかか…
問題 日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1090) 制約条件 n≦100 1≦col[i]≦4 m≦2000 1≦ai,bi≦n -1000≦ci≦1000 1≦k≦10 patternは1〜4からなる長さ10以下の文字列
問題 hxwのグリッドが与えられる。 グリッドのそれぞれには1〜9の数字が書かれている。 このグリッドの(startRow,startCol)を出発して、(goalRow,goalCol)へ行きたい。 一回の移動では、上下左右に何回か動くことができる。 ただし、一回の移動中に通ったマ…
問題 長さLのスキーのコースがある。 n個のジャンプ台があり、それぞれの座標はx[i] ジャンプ台を使うと、x[i]+d[i]に、t[i]の時間をかけて飛ぶことができる。 ただし、ジャンプ台を使うためにはx[i]-p[i]から地上を滑っている必要がある。 スキーヤーが地上…
問題 折れ線がつながってジグザグな一本の線になっている山道がある。 線の左端は(0,0)で、右端のy座標も0である。 二人の登山家が左端の頂点と、右端の頂点を同時に出発して出会いたい。 二人は、常に等しい高さに居るという制約を満たしながら動かなければ…
問題 n個の交差点がm本の双方向に通行可能な道路によって結ばれている。 m本の道路は、 始点s[i],終点t[i],距離w[i]の形式で与えられる。 各交差点にはタクシーがいて、利用料金は距離にかかわらずc[i]、ただし利用距離の限度はそれぞれt[i]である。 このと…
問題概要 CPUには5つの処理部分があり、1クロックごとに別の処理ができる。 与えられた長さnクロックの処理が、それぞれのクロックに使うCPUの部分のテーブルが与えられたとき、この処理を10回行うのに必要な最小のクロックを求めよ。
問題概要 日本語なので本文参照 (http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1058&lang=jp)
問題概要 与えられた重みつき有向グラフにおいて、1番のノードからn番のノードまでの最短路について考える。グラフの重みをk箇所、好きな非負の値に変えることにより最短路の長さをcにしたい。 このような最小のkを求めよ。 n≦100,辺の本数≦1000,c≦1000000を…
問題概要 重み付き無向グラフで表わされる都市と道路がある。 都市1から都市2へ最短距離で帰りたい。この国では内戦がおきて、それぞれの都市はリーダー1またはリーダー2のどちらかを支持している。 安全のために、リーダーの異なる都市への移動は一度だけに…
問題概要 日本語なので本文参照(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0224&lang=jp)自宅から、ケーキ屋とランドマークからなるノードを通り役所まで行く。 ケーキ屋の前を通るときにはそのケーキ屋のケーキを食べ、カロリ…
問題概要 辺に英小文字からなる呪文が書かれた有向グラフがある。 スタートからゴールまでグラフを辿ったときに得られる、「それまでにたどった辺の呪文を並べた」文字列のうち、辞書順で最も先頭に来るものを最強の呪文と呼ぶ。 最強の呪文が一意に決まる場…
本番で9RE出して結局通らなかった問題。 コンストラクタをtypoしてた。ああもおお悔しいなああああああ!!!!! サイコロの実装はかなり綺麗だと思うので参考にしたい方はどうぞ。 問題概要 将軍様が云々。 h*wマスのグリッドのそれぞれに数字が書かれている。 …
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1162昔BFSで書いてTLEだった問題。 隣接リスト使用&アルゴリズムをダイクストラ法に変更したら時間制限内に終わった。久しぶりのダイクストラだったので演算子多重定義の書き方を忘れ…