Submission #1774806

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using node = tuple<ll, int>;
const int inf = numeric_limits<int>::max()/3;

vector< vector<int> > G;
int dist_s[100010];
int dist_t[100010];

void dijkstra(int s,int *dist){
  priority_queue< node, vector<node>, greater<node> > que;
  que.push(node(0,s));
  while(!que.empty()){
    int now,cost;
    tie(cost,now) = que.top();
    que.pop();
    if(cost < dist[now]){
      dist[now] = cost;
      for(int i : G[now]){
        if(cost + 1 < dist[i]){
          que.push(node(cost+1,i));
        }
      }
    }
  }
}

int main(void){
  fill(dist_s,dist_s+100010,inf);
  fill(dist_t,dist_t+100010,inf);
  int n,m,s,t;
  cin >> n >> m >> s >> t;
  --s;--t;
  G.resize(n);
  for(int i = 0;i < m;++i){
    int x,y;
    cin >> x >> y;
    --x;--y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dijkstra(s,dist_s);
  dijkstra(t,dist_t);
  vector< int > vec;
  for(int i = 0;i < n;++i){
    vec.push_back(dist_t[i]);
  }
  sort(vec.begin(),vec.end());
  int mdist = dist_s[t];
  ll res = 0;
  for(int i = 0;i < n;++i){
    int target = mdist - dist_s[i] - 2;
    int cnt =
      upper_bound(vec.begin(),vec.end(),target)
      - lower_bound(vec.begin(),vec.end(),target);
    cnt = max(cnt,0);
    res += cnt;
  }
  cout << res << endl;
  return 0;
}

Submission Info

Judge Result