ABC319 G - Counting Shortest Paths
問題概要
$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$ |
実装上の注意
出力する答えが $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_limits<ll>::max()/2;
void solve() {
int n, m; cin >> n >> m;
unordered_set<ll> edges;
vector<vector<int>> g(n);
rep(i, m) {
ll u, v; cin >> u >> v; u--; v--;
edges.insert(u * n + v);
edges.insert(v * n + u);
g[u].push_back(v);
g[v].push_back(u);
}
vector<pair<int, int>> dist(n); dist[0] = {0, 0};
rep(i, n-1) dist[i+1] = {inf, i+1};
unordered_set<int> unvisited; rep(i, n-1) unvisited.insert(i + 1);
queue<int> q; q.push(0);
while (!q.empty()) {
auto x = q.front(); q.pop();
vector<int> visited;
for (auto& y : unvisited) {
if (!edges.count(1LL * x * n + y)) {
visited.emplace_back(y);
dist[y].first = dist[x].first + 1;
q.push(y);
}
}
for (auto& y : visited) {
unvisited.erase(y);
}
}
if (dist[n-1].first == inf) {
cout << -1 << '\n';
return;
}
sort(dist.begin(), dist.end());
vector<int> ind(n); rep(i, n) ind[dist[i].second] = i;
vector<ll> cnt(n+1); cnt[0] = 1; cnt[1] = -1;
int maxdist = 0; rep(i, n) if (dist[i].first != inf) maxdist = dist[i].first;
vector<pair<int, int>> sec(maxdist+2, {n, n}); sec[0] = {0, 0};
rep(i, n) {
if (i==n-1 || dist[i].first != dist[i+1].first) {
if (dist[i].first != inf) sec[dist[i].first].second = i+1;
if (i != n-1 && dist[i+1].first != inf) sec[dist[i+1].first].first = i+1;
}
}
rep(i, n) {
if (dist[i].first == inf) break;
int I = dist[i].second;
cnt[sec[dist[i].first+1].first] += cnt[i];
cnt[sec[dist[i].first+1].first] %= mod;
cnt[sec[dist[i].first+1].second] -= cnt[i];
cnt[sec[dist[i].first+1].second] %= mod;
for (auto& J : g[I]) {
int j = ind[J];
if (dist[i].first + 1 == dist[j].first) {
cnt[j] -= cnt[i];
cnt[j] %= mod;
cnt[j+1] += cnt[i];
cnt[j+1] %= mod;
}
}
cnt[i+1] += cnt[i];
cnt[i+1] %= mod;
}
cout << (cnt[ind[n-1]]%mod+mod)%mod << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}
コメント
コメントを投稿