[AtCoder] ABC 061 D – Score Attack
問題
方針
グラフの問題では最短距離を答える問題が多いと思いますが、今回は違います。このような問題では、重みの符号を反転させ、最短経路問題に帰着させます。これは、\( y = f(x) \) の最大化問題を \( y = -f(x) \) の最小化問題として解くようなものだと思います。
与えられるグラフでは負閉路が存在する可能性があるので、負閉路の検出をする必要があります。到達可能な負閉路が存在したとしても、頂点 \( 1 \) から頂点 \( N \) のパスに負閉路が存在しなければ、スコアが発散することはありません。
コード
提出したコード
ベルマン-フォード法
struct Edge { ll cost; int from, to; Edge(){} Edge(int from, int to, ll cost) : from(from), to(to), cost(cost){} }; Edge e[2 * MAX]; ll d[MAX]; // 到達可能な負閉路があれば true bool bellman_ford() { for (int i = 0; i < MAX; i++) { d[i] = INF; } // 頂点 0 からスタート d[0] = 0; for (int i = 0; i < 2 * N; i++) { for (int j = 0; j < M; j++) { if(d[e[j].from] != INF && d[e[j].to] > d[e[j].from] + e[j].cost) { d[e[j].to] = d[e[j].from] + e[j].cost; if(i >= N - 1 && e[j].to == N - 1) return true; } } } return false; }
ディスカッション
コメント一覧
まだ、コメントがありません