Advertisement
Guest User

Untitled

a guest
Feb 24th, 2019
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <unordered_map>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. vector<vector<int> > g;
  10. unordered_map<string, int> v;
  11.  
  12.  
  13. /**
  14.  * Создать пустой (без рёбер) n-вершинный граф.
  15.  */
  16. void set_empty(int n) {
  17.     g.clear();
  18.     for (int i = 0; i < n; ++i) {
  19.         vector<int> x;
  20.         g.push_back(x);
  21.     }
  22. }
  23.    
  24. /**
  25.  * Прочитать матрицу смежности и добавить рёбра из неё в граф.
  26.  */
  27. void read_matrix() {
  28.     for (int i = 0; i < g.size(); ++i) {
  29.         for (int j = 0; j < g.size(); ++j) {
  30.             int x;
  31.             cin >> x;
  32.             if (x) {
  33.                 g[i].push_back(j);
  34.             }
  35.         }
  36.     }
  37. }
  38.  
  39. int read_name() {
  40.     string s;
  41.     cin >> s;
  42.     int sz = v.size();
  43.     int &x = v[s];
  44.     if (sz < v.size()) {
  45.         x = sz;
  46.     }
  47.     return x;
  48. }
  49.  
  50. /**
  51.  * Прочитать список рёбер и добавить рёбра в граф.
  52.  */
  53. void read_edges(int m) {
  54.     for (;m;--m) {
  55.         int x = read_name();
  56.         {
  57.             string s;
  58.             cin >> s;
  59.         }
  60.         int y = read_name();
  61.         while (g.size() <= v.size()) {
  62.             g.emplace_back();
  63.         }
  64.         g[x].push_back(y);
  65.     }
  66. }
  67.    
  68. int main() {
  69.     int m;
  70.     cin >> m;
  71.     read_edges(m);
  72.     int n = v.size();
  73.     int s = read_name();
  74.     int t = read_name();
  75.     if (s == t) {
  76.         cout << "0";
  77.         return 0;
  78.     }
  79.     if (n < v.size()) {
  80.         cout << "-1";
  81.         return 0;
  82.     }
  83.      
  84.     vector<int> vc(1, s);
  85.     vector<int> vn;
  86.     vector<int> d(n, 100);
  87.     d[s] = 0;
  88.  
  89.     while (d[t] == 100 && !vc.empty()) {
  90.         for (auto x : vc) {
  91.             auto dn = d[x] + 1;
  92.             for (auto y : g[x]) {
  93.                 if (dn < d[y]) {
  94.                     vn.push_back(y);
  95.                     d[y] = dn;
  96.                 }
  97.             }
  98.         }
  99.         vn.swap(vc);
  100.         vn.clear();
  101.     }
  102.  
  103.     cout << (d[t] == 100 ? -1 : d[t]);
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement