AtCoder Beginner Contest 051 D - 今日から始める競プロ日記
はじめに
過去問の400点問題を埋めていく。
今日は AtCoder Beginner Contest (ABC) 051 のD問題を解いてみた。
D - Candidates of No Shortest Paths
N 頂点 M 辺の重み付き無向連結グラフが与えられる。
頂点 ai と頂点 bi は距離 ci で結ばれている。
このとき、すべての異なる2頂点間における、どの最短経路においても含まれない辺の数を求める問題。
つまり、すべての最短経路において絶対に通らない辺の数を求めたい。
条件は以下。
2 <= N <= 100 N-1 <= M <= min(N(N-1)/2, 1000) 1 <= ai, bi <= N 1 <= ci <= 1000
今回の解き方
以下の記事を参考。めちゃくちゃ分かりやすい。
まず、最短経路において絶対に通らない辺とは何かを考える。
それは ai から bi に移動するとき、直接 ai → bi に行くより、ai → いくつかの頂点 → bi というような迂回路のほうが距離が短いときである。
これを以下の図で説明。
A → B の距離は 5。それに対して、C を経由する経路（A → C → B）の距離は 3 （1 + 2）。
つまり、どんなときであろうと A から B に行きたいとき（もしくは B から A に行きたいとき）、 距離が3である C を経由する経路が最短経路となる。
したがって、最短経路を求める際、辺 A → B は絶対に通らない辺ということになる。
このような辺を数えることが今回の問題である。
ワーシャルフロイド法
以下の記事も参考。ありがたい。
ワーシャルフロイド法はある頂点からある頂点までの最短経路をO(N^3)で求めるアルゴリズムである。
ある頂点 I からある頂点 J までの最短距離を求めるとき、 頂点 I から頂点 J へ直接行く経路と、ある頂点 K を経由した経路を比較して、距離が短いほうを記録していく。
この処理をすべての頂点で行う。
つまりfor文3つ。
コード
上でも引用したけんちょんさんのコードを参考に書きました。
もう一度載せます。
以下がこの記事を参考に書いたコードである。
#include <iostream>
using namespace std;
int main()
{
const int INF = 1<<29;
int N, M;
cin >> N >> M;
int a[1001] = {0};
int b[1001] = {0};
int c[1001] = {0};
int dist[101][101] = {0};
//ワーシャルフロイド法の初期化
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
dist[i][j] = INF;
}
dist[i][i] = 0; //自分への距離はゼロ
}
for(int i = 0; i < M; i++)
{
cin >> a[i] >> b[i] >> c[i];
a[i]--; b[i]--; //インデックスのベースを１→０
dist[a[i]][b[i]] = c[i];
dist[b[i]][a[i]] = c[i];
}
//ワーシャルフロイド法
for(int k = 0; k < N; k++)
{
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
//この時点でdistには各頂点間の最短経路が入ってる
//a[i]→b[i]間の距離が更新されている場合は、迂回路のほうが最短経路であるということ
//つまりそのa[i]→b[i]は、いかなる経路においても最短経路として使われない経路である
//(a[i]→b[i]を移動したいとき迂回経路のほうが最短経路となっているということ)
int cnt = 0;
for(int i = 0; i < M; i++)
{
if(c[i] > dist[a[i]][b[i]]) cnt++;
}
cout << cnt << endl;
return 0;
}
おわりに
グラフの問題はまだまだ慣れていないからとりあえず数をこなしていきたい。
