Submission #2124231

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<climits>
#include<cassert>
#include<set>
#include<tuple>
using namespace std;

int d[100], num[100];
vector<vector<int>> g(100);
const int INF = INT_MAX / 2;
#define MOD 1000000007

int main()
{
	int n, a, b, m, x, y;
	cin >> n >> a >> b >> m;
	a--;
	b--;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		x--;
		y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 0; i < n; i++) {
		d[i] = INF;
		num[i] = 0;
	}
	d[a] = 0;
	num[a] = 1;
	queue<int> q;
	q.push(a);
	while (!q.empty()) {
		int s = q.front();
		q.pop();
		for (int i = 0; i < g[s].size(); i++) {
			int t = g[s][i];
			if (d[t] == INF) {
				d[t] = d[s] + 1;
				(num[t] += num[s]) %= MOD;
				q.push(t);
			}
			else if (d[t] == d[s] + 1) {
				(num[t] += num[s]) %= MOD;
			}
		}
	}
	cout << num[b] << endl;
	return 0;
}

Submission Info

Judge Result