AOJ2608 Minus One

Minus One | Aizu Online Judge

Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory

$G$に$e$を付け加えて無向グラフにおける$s$から$t$への最短路の長さより$1$だけ大きいものの個数を答える．これはつまり，パスを貼った時に最短経路長が$1$小さくなるものである．

$s$からの最短経路長を$d[i]$，$t$からの最短経路長を$d2[i]$とする．点$a$と点$b$を結んだ場合，$s \to a \to b \to t$という経路を行くとすると，コストは$d[a] + 1 + d2[b]$となる．この時$s \to t$の最短経路長$+1$となる経路は， $$ \begin{eqnarray} d[t] - 1 &=& d[a] + 1 + d2[b] \\ d2[b] &=& d[t] - 2 - d[a] \end{eqnarray} $$ が条件となる．愚直に$a, b$のペアを列挙して確認すると$O(n ^2)$で間に合わないが，点$a$を決めた時に，経路長$1$少なくなる$b$の選び方は$d[t] - 2 - d[a]$となる$d2[i]$の個数と決まるので，先に$d2[i]$をカウントしておくと$O(n)$で求められる．最短経路を求めるのが一番時間がかかるので全体で$O(n logn)$．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct edge {
  int from,to;
  int cost;

  edge(int t,int c) : to(t),cost(c) {}
  edge(int f,int t,int c) : from(f),to(t),cost(c) {}

  bool operator<(const edge &e) const {
      return cost < e.cost;
  }
};

vector<edge> G[100005];
int d[100005], d2[100005], cnt[100005];

void dijkstra(int s) {
  priority_queue<P, vector<P>, greater<P> > que;
  rep(i, 100005) d[i] = INF;
  
  que.push(mp(0, s));
  d[s] = 0;

  while(que.size()) {
      P p = que.top(); que.pop();
      int cost = p.first;
      int v = p.second;

      if(d[v] < cost) continue;

      rep(i, G[v].size()) {
          edge e = G[v][i];
          if(d[e.to] > d[v] + e.cost) {
              d[e.to] = d[v] + e.cost;
              que.push(mp(d[e.to], e.to));
          }
      }
  }
}

int main() {
  int n, m;
  cin >> n >> m;

  int s, t;
  cin >> s >> t;
  s--; t--;

  rep(i, m) {
      int a, b;
      cin >> a >> b;
      a--; b--;

      G[a].push_back(edge(b, 1));
      G[b].push_back(edge(a, 1));
  }

  dijkstra(s);
  rep(i, n) d2[i] = d[i];

  dijkstra(t);
  rep(i, n) swap(d[i], d2[i]);

  memset(cnt, 0, sizeof(cnt));
  rep(i, n) {
      if(d2[i] == INF) continue;
      cnt[d2[i]]++;
  }

  ll ans = 0;
  rep(i, n) {
      if(d[i] == INF || d2[i] == INF) continue;
      int x = d[t] - 2 - d[i];

      if(x >= 0) {
          ans += cnt[x];
      }
  }

  cout << ans << endl;

  return 0;
}

経路復元とか色々していて，色々考えた後に書き直したら非常にスッキリして面白いと思った．但し解くのに時間がかかりすぎている…

Jun 6th, 2016
350, aoj-icpc, dijkstra, グラフ