Submission #3782748


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)
typedef long long ll;
typedef pair <int, int> P;
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;


VI v[110];
int n;
int a, b, d;
int m;

int main(){
	cin >> n;
	cin >> a >> b;
	a--; b--;
	cin >> m;
	VVI c(110, VI(110, 100000));
	REP(i, m) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		v[x].push_back(y);
		v[y].push_back(x);
		c[x][y] = 1;
		c[y][x] = 1;
	}
	
	REP(k, 100)REP(i, 100)REP(j, 100) c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
	d = c[a][b];
	VI ans(110, 0);
	ans[a] = 1;
	REP(i, d) {
		VI res(110, 0);
		REP(j, 100) {
			if (ans[j] == 0)continue;
			for (int p : v[j]) {
				res[p] += ans[j];
			}
		}
		ans = res;
	}
	cout << ans[b] << endl;


	return 0;
}

Submission Info

Submission Time
Task C - 正直者の高橋くん
User toku
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1238 Byte
Status WA
Exec Time 3 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 31
WA × 1
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 2 ms 256 KB
subtask0_sample_02.txt AC 2 ms 256 KB
subtask1_01.txt AC 3 ms 256 KB
subtask1_02.txt AC 3 ms 256 KB
subtask1_03.txt AC 2 ms 256 KB
subtask1_04.txt WA 3 ms 256 KB
subtask1_05.txt AC 3 ms 256 KB
subtask1_06.txt AC 2 ms 256 KB
subtask1_07.txt AC 2 ms 256 KB
subtask1_08.txt AC 3 ms 256 KB
subtask1_09.txt AC 3 ms 256 KB
subtask1_10.txt AC 3 ms 256 KB
subtask1_11.txt AC 3 ms 256 KB
subtask1_12.txt AC 3 ms 256 KB
subtask1_13.txt AC 3 ms 256 KB
subtask1_14.txt AC 3 ms 256 KB
subtask1_15.txt AC 3 ms 256 KB
subtask1_16.txt AC 3 ms 256 KB
subtask1_17.txt AC 3 ms 256 KB
subtask1_18.txt AC 3 ms 256 KB
subtask1_19.txt AC 3 ms 256 KB
subtask1_20.txt AC 3 ms 256 KB
subtask1_21.txt AC 3 ms 256 KB
subtask1_22.txt AC 3 ms 256 KB
subtask1_23.txt AC 3 ms 256 KB
subtask1_24.txt AC 3 ms 256 KB
subtask1_25.txt AC 3 ms 256 KB
subtask1_26.txt AC 3 ms 256 KB
subtask1_27.txt AC 3 ms 256 KB
subtask1_28.txt AC 3 ms 256 KB
subtask1_29.txt AC 2 ms 256 KB
subtask1_30.txt AC 2 ms 256 KB