Submission #2748633

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <queue>
#include <stack>
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repr(i, a, n) for(int (i) = (int)(a);(i) > (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, n) &x[0], &x[n]
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define pb push_back
#define EPS (1e-20)
#define INF 2147483647
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using namespace std;


int N;
int a, b;
int M;
VI g[110];
VI dag[110];
VI tpDAG;
int dp[110];


void makeDAG(){
	int d[110] = {};
	bool u[110] = {};
	queue<int> q;
	d[a] = 0;
	u[a] = true;
	q.push(a);
	while(!q.empty()){
		int pn = q.front();
		q.pop();
		for(int nn : g[pn])
			if(!u[nn]) d[nn] = d[pn] + 1, u[nn] = true, q.push(nn);
	}
	rep(i, 0, N)
		for(int n : g[i])
			if(d[i]+1 == d[n]) dag[i].pb(n);
}


void tpSort(){
	int eCnt[110] = {};
	rep(i, 0, N)
		for(int n : dag[i]) eCnt[n]++;
	stack<int> s;
	rep(i, 0, N)
		if(!eCnt[i]) s.push(i);
	while(!s.empty()){
		tpDAG.pb(s.top());
		s.pop();
		for(int n : dag[tpDAG.back()]){
			eCnt[n]--;
			if(!eCnt[n]) s.push(n);
		}
	}
}


void makeDP(){
	for(int n : dag[a]) dp[n] = 1;
	rep(i, 1, N)
		for(int n : dag[tpDAG[i]])
			(dp[n]+=(dp[tpDAG[i]]%MOD))%=MOD;
}


signed main(){
	cin >> N;
	cin >> a >> b, a--, b--;
	cin >> M;
	rep(i, 0, M){
		int x, y;
		cin >> x >> y;
		g[--x].pb(--y);
		g[y].pb(x);
	}

	makeDAG();
	tpSort();
	makeDP();

	cout << dp[b] << endl;

	return 0;
}

Submission Info

Judge Result