Contest Duration: ~ (local time) (120 minutes) Back to Home

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 2015-04-11 21:13:21+0900 C - 正直者の高橋くん cympfh C++11 (GCC 4.9.2) 100 1700 Byte AC 29 ms 932 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory