Submission #383574


Source Code Expand

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define loop for(;;)
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;
#define inf (1e9)
#define eps (1e-9)
using Integer = long long;
using Real = long double;
const Real PI = acos(-1);

template<class S, class T> inline
ostream& operator<<(ostream&os, pair<S,T> p) {
  os << '(' << p.first << ", " << p.second << ')';
  return os;
}

template<class T> inline
ostream& operator<<(ostream&os, vector<T> v) {
  if (v.size() == 0) {
    os << "(empty)";
    return os;
  }
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

template<class T> inline
istream& operator>>(istream&is, vector<T>&v) {
  rep (i, v.size()) is >> v[i];
  return is;
}

int dx[] = { -1, 0, 1, 0 };
int dy[] = {  0, -1, 0, 1 };

using vi = vector<int>;
using vvi = vector<vi>;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout.setf(ios::fixed);
  cout.precision(10);

  int n; cin >> n;
  vi d(n, inf);
  vi c(n, 0);

  vvi dl(n);

  int s, t; cin >> s >> t;
  --s; --t;

  int m; cin >> m;
  rep (i, m) {
    int u, v; cin >> u >> v; --u; --v;
    dl[u].push_back(v);
    dl[v].push_back(u);
  }

  const int M =  1000000007;

  d[s] = 0;
  c[s] = 1;
  queue<int> q; q.push(s);
  while (not q.empty()) {
    int u = q.front(); q.pop();
    for (int v: dl[u]) {
      if (d[v] > d[u] + 1) {
        c[v] = c[u];
        d[v] = d[u] + 1;
        q.push(v);
      }
      else if (d[v] == d[u] + 1) {
        c[v] += c[u];
        c[v] %= M;
      }
    }
  }

  cout << c[t] << endl;

  return 0;
}

Submission Info

Submission Time
Task C - 正直者の高橋くん
User cympfh
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1700 Byte
Status
Exec Time 29 ms
Memory 932 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 25 ms 924 KB
subtask0_sample_02.txt 25 ms 924 KB
subtask1_01.txt 26 ms 800 KB
subtask1_02.txt 26 ms 796 KB
subtask1_03.txt 25 ms 928 KB
subtask1_04.txt 27 ms 800 KB
subtask1_05.txt 25 ms 932 KB
subtask1_06.txt 25 ms 928 KB
subtask1_07.txt 25 ms 800 KB
subtask1_08.txt 24 ms 924 KB
subtask1_09.txt 25 ms 928 KB
subtask1_10.txt 26 ms 804 KB
subtask1_11.txt 24 ms 932 KB
subtask1_12.txt 27 ms 800 KB
subtask1_13.txt 26 ms 924 KB
subtask1_14.txt 26 ms 796 KB
subtask1_15.txt 25 ms 796 KB
subtask1_16.txt 25 ms 804 KB
subtask1_17.txt 25 ms 812 KB
subtask1_18.txt 24 ms 920 KB
subtask1_19.txt 25 ms 800 KB
subtask1_20.txt 26 ms 804 KB
subtask1_21.txt 24 ms 924 KB
subtask1_22.txt 29 ms 736 KB
subtask1_23.txt 26 ms 800 KB
subtask1_24.txt 26 ms 796 KB
subtask1_25.txt 26 ms 800 KB
subtask1_26.txt 24 ms 924 KB
subtask1_27.txt 24 ms 804 KB
subtask1_28.txt 25 ms 932 KB
subtask1_29.txt 24 ms 928 KB
subtask1_30.txt 24 ms 928 KB