Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_set>
- #include <unordered_map>
- #include <string>
- using namespace std;
- vector<vector<int> > g;
- unordered_map<string, int> v;
- /**
- * Создать пустой (без рёбер) n-вершинный граф.
- */
- void set_empty(int n) {
- g.clear();
- for (int i = 0; i < n; ++i) {
- vector<int> x;
- g.push_back(x);
- }
- }
- /**
- * Прочитать матрицу смежности и добавить рёбра из неё в граф.
- */
- void read_matrix() {
- for (int i = 0; i < g.size(); ++i) {
- for (int j = 0; j < g.size(); ++j) {
- int x;
- cin >> x;
- if (x) {
- g[i].push_back(j);
- }
- }
- }
- }
- int read_name() {
- string s;
- cin >> s;
- int sz = v.size();
- int &x = v[s];
- if (sz < v.size()) {
- x = sz;
- }
- return x;
- }
- /**
- * Прочитать список рёбер и добавить рёбра в граф.
- */
- void read_edges(int m) {
- for (;m;--m) {
- int x = read_name();
- {
- string s;
- cin >> s;
- }
- int y = read_name();
- while (g.size() <= v.size()) {
- g.emplace_back();
- }
- g[x].push_back(y);
- }
- }
- int main() {
- int m;
- cin >> m;
- read_edges(m);
- int n = v.size();
- int s = read_name();
- int t = read_name();
- if (s == t) {
- cout << "0";
- return 0;
- }
- if (n < v.size()) {
- cout << "-1";
- return 0;
- }
- vector<int> vc(1, s);
- vector<int> vn;
- vector<int> d(n, 100);
- d[s] = 0;
- while (d[t] == 100 && !vc.empty()) {
- for (auto x : vc) {
- auto dn = d[x] + 1;
- for (auto y : g[x]) {
- if (dn < d[y]) {
- vn.push_back(y);
- d[y] = dn;
- }
- }
- }
- vn.swap(vc);
- vn.clear();
- }
- cout << (d[t] == 100 ? -1 : d[t]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement