Submission #2999149

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
//typedef pair<ll,int> P;
int N,a,b,M,x,y,inf = 1e9+7;
int D[101][101];
ll dp[101] = {0};

int main(){
	cin >> N >> a >> b >> M;
	vector<vector<int>> v(101);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			if(i!=j) D[i][j] = inf;
			else D[i][j] = 0;
		}
	}
	for(int i=0;i<M;i++){
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
		D[x][y] = 1;
		D[y][x] = 1;
	}
	for(int k=1;k<=N;k++){
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				D[i][j] = min(D[i][j],D[i][k]+D[k][j]);
			}
		}
	}
	dp[a] = 1;
	queue<int> Q;//{場合の数，頂点}
	Q.push(a);
	int visited[101] = {0};
	while(Q.size()>0){
		//P t = Q.front();
		int n = Q.front();
		Q.pop();
		for(int i=0;i<v[n].size();i++){
			if(D[a][n]+D[n][v[n][i]] == D[a][v[n][i]]){
				dp[v[n][i]] = (dp[v[n][i]]+dp[n])%inf;
				if(visited[v[n][i]]==0) Q.push(v[n][i]);
				visited[v[n][i]] = 1;
			}
		}
	}
//	for(int i=1;i<=N;i++) cout << dp[i] << (i==N? "\n":" ");
	cout << dp[b] << endl;
}

Submission Info

Judge Result