ぽえの競プロノート

作成日: 2026-05-13 最終更新: 2026-05-13 問題へのリンク 問題概要 $N$ 頂点の完全グラフから $M$ 辺を取り除いたとき、頂点 $1$ から頂点 $N$ への最短経路の個数を求めよ。 ・ $2 \le N \le 2 \times 10^5$ ・ $0 \le M \le \min(2 \times 10^5, \binom{N}{2})$ 575 点 解説 全頂点に対して頂点 $1$ からの最短距離が分かれば、距離が小さい順に最短経路の個数を決定できる。 頂点 $1$ からBFS をする。このとき、頂点から出ている辺をすべて見るのではなく、未訪問の頂点のうち、辺が存在するものに遷移すれば $O(N)$ 回の遷移で済む。 頂点 $1$ からの最短距離が分かれば、最短距離で頂点をソートして区間加算・一点取得を高速にできるデータ構造を用いて、最短距離が $k$ の頂点から最短距離が $k+1$ の頂点に遷移することで計算できる。加算をする区間は、取得する位置より後にあるので、いもす法を適用して $O(N+M)$ で計算できる。 全体の計算量は $O(M+ N \log{N})$ 。 サンプル $1$ サンプル $2$ (5/14 追記) ソートはバケットソートを用いることで $O(N)$ でできるため、全体の計算量は $O(N+M)$ にすることができる。 実装上の注意 出力する答えが $0$ の時に $-1$ を出力する実装にしていると、答えが $998244353$ の倍数の時にも $-1$ を出力してしまうので、距離の配列などを使って頂点 $N$ まで到達できるかどうかを判定しておくとよい。 AC コード 提出へのリンク #include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (ll i=0; i<(ll)(n); i++) const ll mod = 998244353; const int inf = numeric_limits<int>::max()/2; const ll INF = numeric_lim...