Submission #2994992

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll MOD = 1e9 + 7;

template <typename T>
void warshallFloyd(T& d){
    for (int i = 0; i < d.size(); i++) d[i][i] = 0;

    for (int k = 0; k < d.size(); k++){
		for (int i = 0; i < d.size(); i++){
	    	for (int j = 0; j < d.size(); j++){
				d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
	    	}
		}
    }
}

template <typename T1, typename T2>
ll func (int s, int g, T1& d, T2& list, int cost, vector<ll>& mem) {
	if (s == g) return 1;
	if (mem[s] != -1) return mem[s];

	ll cnt = 0;
	for (int i = 0; i < list[s].size(); i++) {
		if (d[list[s][i]][g] != (cost - 1)) continue;

		cnt += func(list[s][i], g, d, list, cost - 1, mem);
		cnt %= MOD;
	}

	if (mem[s] == -1) {
		mem[s] = cnt;
	}

	return cnt;
}

int main() {
	const ll INF = 1e9;
	int N, a, b, M;
	cin >> N;
	cin >> a >> b;
	cin >> M;
	vector<vector<ll>> d(N + 1, vector<ll>(N + 1, INF));
	vector<vector<int>> list(N + 1);
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		d[x][y] = 1;
		d[y][x] = 1;
		list[x].push_back(y);
		list[y].push_back(x);
	}

	warshallFloyd(d);

	vector<ll> mem(N + 1, -1);
	ll res = 0;
	for (int i = 0; i < list[a].size(); i++) {
		if (d[list[a][i]][b] != (d[a][b] - 1)) continue;

		res += func(list[a][i], b, d, list, d[a][b] - 1, mem);
		res %= MOD;
	}

	cout << res << endl;
	return 0;
}

Submission Info

Judge Result