Cod sursa(job #2963349)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 10 ianuarie 2023 21:06:21
Problema NFA Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("nfa.in");
ofstream fout("nfa.out");

const int kN = 300;
const int kLen = 150;
const int kSigma = 26;
bitset<kN> isFinalState;
vector<int> graph[kN][kSigma];
string word;
bitset<kLen> vis[kN];

bool dfs(int state, int index) {
  if (index == (int)word.size()) {
    if (isFinalState[state]) {
      return true;
    }
    return false;
  }

  int edgeType = word[index] - 'a';

  for (const int &newState : graph[state][edgeType]) {
    if (!vis[newState][index]) {
      vis[newState][index] = true;

      if (dfs(newState, index + 1)) {
        return true;
      }
    }
  }

  return false;
}

int main() {
  int n, m, k, s;
  fin >> n >> m >> k >> s;

  s -= 1;

  for (int i = 0; i < k; ++i) {
    int state;
    fin >> state;
    isFinalState[state - 1] = true;
  }

  for (int i = 0; i < m; ++i) {
    int u, v;
    char w;
    fin >> u >> v >> w;
    graph[u - 1][w - 'a'].emplace_back(v - 1);
  }

  int q;
  fin >> q;

  for (int i = 0; i < q; ++i) {
    fin >> word;

    for (int state = 0; state < n; ++state) {
      vis[state].reset();
    }

    if (dfs(s, 0)) {
      fout << "1\n";
    } else {
      fout << "0\n";
    }
  }

  fin.close();
  fout.close();
  return 0;
}