[ABC021C] 正直者の高橋くん 题解

· · 题解

尝试使用类似 DP 的东西计数。设 c_i 为到达 i 的方案数，更新时若 d_i=d_u+1 那么 c_i\gets c_i+c_u。

由于这个图边权只有 1，所以直接进行 BFS 实现上述过程。时间复杂度 O(n+m)。

放代码：


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=1e9+7;
main(){
  ios::sync_with_stdio(false);
  int n,s,b,m; cin>>n>>s>>b>>m,s--,b--;
  vector<vector<int> > g(n);
  for(int i=0;i<m;i++){
    int x,y; cin>>x>>y,x--,y--;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  } // 用 vector 存图
  vector<int> v(n),a(n),c(n);
  queue<int> q; q.emplace(s),v[s]=c[s]=1;
  while(!q.empty()){ // 广搜过程
    int x=q.front(); q.pop();
    for(int h:g[x]){
      if(!v[h])v[h]=1,a[h]=a[x]+1,q.emplace(h);
      if(a[h]==a[x]+1)c[h]=(c[h]+c[x])%P; // 更新答案
    }
  }
  cout<<c[b]<<endl; // 输出答案
  return 0;
}