AOJ 2608 - Minus One
問題
問題概要
頂点辺の無向グラフと頂点番号が与えられる。この無向グラフに辺を1つ足すことによって、もとのグラフにおけるからへの最短経路長よりも1だけ短くすることができるようなは何通りあるか。
- からへはたどり着けることが保証される
アイデア
からの最短経路をdijkstra法で求めて、その距離を見ながらごにゃごにゃやろうとして、沼にはまった。
2頂点からの最短経路を使って考えるとスッキリして分かりやすい。からの最短経路とからの最短経路を求めておく(それぞれと表す)。
すると、という辺を作ったときに、条件を満たしているかどうか確かめるには、となっているかどうかを確かめればよい。ただ、全ての頂点の組み合わせを試しているとかかってしまい、間に合わない。
ここで、等式に注目してみると右辺はconst.なので、という形になっているので、それぞれから最短経路長がの 頂点の個数を数え上げておいて、その積を足せばよく、で解が求まる。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second typedef pair<int,int> pi; const int N=100000, M=300000; const int INF=12345678; int d[2][N]; vector<int> G[N]; int d_ct=0; void dijkstra(int s) { // dijkstra priority_queue<pi,vector<pi>,greater<pi>> que; fill(d[d_ct],d[d_ct]+N,INF); d[d_ct][s]=0; que.push(pi(0,s)); while(!que.empty()) { pi p=que.top(); que.pop(); int v=p.se; if(d[d_ct][v]<p.fi) continue; rep(i,G[v].size()) { int nx=G[v][i]; if(d[d_ct][nx]>d[d_ct][v]+1) { d[d_ct][nx]=d[d_ct][v]+1; que.push(pi(d[d_ct][nx],nx)); } } } ++d_ct; } int cts[N]={0}, ctt[N]={0}; int main() { int n,m,s,t; scanf(" %d %d %d %d", &n, &m, &s, &t); --s; --t; rep(i,m) { int x,y; scanf(" %d %d", &x, &y); --x; --y; G[x].pb(y); G[y].pb(x); } dijkstra(s); dijkstra(t); rep(i,n) if(d[0][i]<N) ++cts[d[0][i]]; rep(i,n) if(d[1][i]<N) ++ctt[d[1][i]]; ll ans=0; rep(i,d[0][t]-1) ans+=(ll)cts[i]*ctt[d[0][t]-2-i]; cout << ans << endl; return 0; }