Submission #3877957


Source Code Expand

Copy
#include <bits/stdc++.h>
#define N 1000000007
using namespace std;

int n, m, a, b;
int memo[105][105] = {0};
bool ch[105] = {0};
int cnt[105] = {0};
int dis[105] = {0};
vector<int> edge[105];

int solve();

int main() {
  cin >> n >> a >> b >> m;
  --a, --b;
  for(int i = 0; i < n; ++i) dis[i] = 100000;
  for(int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    if(memo[x][y] == 0) {
      edge[x].push_back(y);
      edge[y].push_back(x);
    }
    ++memo[x][y];
    ++memo[y][x];
  }
  ++cnt[a];
  dis[a] = 0;
  cout << solve() << endl;
  return 0;
}

int solve() {
  queue<int> qu;
  qu.push(a);
  while(qu.size() > 0) {
    int now = qu.front();
    qu.pop();
    for(int i = 0; i < edge[now].size(); ++i) {
      int nextn = edge[now][i];
      if(dis[now] + 1 < dis[nextn]) {
        qu.push(nextn);
        dis[nextn] = dis[now] + 1;
        cnt[nextn] = 0;
      }
      if(dis[nextn] == dis[now] + 1) {
        cnt[nextn] += cnt[now] * memo[now][nextn];
        cnt[nextn] %= N;
      }
    }
  }
  return cnt[b];
}

Submission Info

Submission Time
Task C - 正直者の高橋くん
User m_tsubasa
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1104 Byte
Status
Exec Time 2 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt
All 100 / 100 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 1 ms 256 KB
subtask0_sample_02.txt 1 ms 256 KB
subtask1_01.txt 1 ms 256 KB
subtask1_02.txt 1 ms 256 KB
subtask1_03.txt 1 ms 256 KB
subtask1_04.txt 1 ms 256 KB
subtask1_05.txt 1 ms 256 KB
subtask1_06.txt 1 ms 256 KB
subtask1_07.txt 1 ms 256 KB
subtask1_08.txt 1 ms 256 KB
subtask1_09.txt 1 ms 256 KB
subtask1_10.txt 1 ms 256 KB
subtask1_11.txt 1 ms 256 KB
subtask1_12.txt 1 ms 256 KB
subtask1_13.txt 1 ms 256 KB
subtask1_14.txt 1 ms 256 KB
subtask1_15.txt 1 ms 256 KB
subtask1_16.txt 1 ms 256 KB
subtask1_17.txt 1 ms 256 KB
subtask1_18.txt 1 ms 256 KB
subtask1_19.txt 2 ms 256 KB
subtask1_20.txt 2 ms 256 KB
subtask1_21.txt 2 ms 256 KB
subtask1_22.txt 1 ms 256 KB
subtask1_23.txt 1 ms 256 KB
subtask1_24.txt 1 ms 256 KB
subtask1_25.txt 1 ms 256 KB
subtask1_26.txt 1 ms 256 KB
subtask1_27.txt 1 ms 256 KB
subtask1_28.txt 1 ms 256 KB
subtask1_29.txt 1 ms 256 KB
subtask1_30.txt 1 ms 256 KB