Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, m, k;
- const int MOD = 1e9 + 7;
- vector < bool > is_terminal;
- vector < vector < pair < int , char > > > g;
- int ans = 0;
- void bfs() {
- queue < pair < int, string > > q;
- q.push({0, ""});
- while (!q.empty()) {
- auto e = q.front();
- q.pop();
- if (e.second.size() == k && is_terminal[e.first]) {
- ans = (ans + 1) % MOD;
- } else {
- int v = e.first;
- string s = e.second;
- for (auto t : g[v]) {
- q.push({t.first, s + t.second});
- }
- }
- }
- cout << ans;
- }
- int main() {
- freopen("numwords.in", "r", stdin);
- freopen("numwords.out", "w", stdout);
- cin >> n >> m;
- is_terminal.resize(n, false);
- g.resize(n);
- for (int i = 0; i < m; i++) {
- int a, b;
- char c;
- cin >> a >> c >> b;
- a--; b--;
- g[a].push_back({b, c});
- }
- int t;
- cin >> t;
- for (int i = 0; i < t; i++) {
- int e;
- cin >> e;
- e--;
- is_terminal[e] = true;
- }
- cin >> k;
- bfs();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement