Advertisement
Josif_tepe

Untitled

Nov 2nd, 2021
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <iostream>
  2. #include<ctime>
  3. #include<map>
  4. #include<vector>
  5. #include<queue>
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10.     int n,r;
  11.     cin>>n>>r;
  12.     vector <int> g[n+1];
  13.     for(int i=0;i<r;i++)
  14.     {
  15.         int a,b;
  16.         cin>>a>>b;
  17.         g[a].push_back(b);
  18.         g[b].push_back(a);
  19.     }
  20.     map<vector<int>,bool> m;
  21.     int t;
  22.     cin>>t;
  23.     vector <int> v;
  24.     for(int i=0;i<t;i++)
  25.     {
  26.         int a,b,c;
  27.         cin>>a>>b>>c;
  28.         v.push_back(a);
  29.         v.push_back(b);
  30.         v.push_back(c);
  31.         m[v]=true;
  32.         v.clear();
  33.     }
  34.     queue<int> q;
  35.     q.push(-1);
  36.     q.push(0);
  37.     q.push(0);
  38.     bool visited[n][n];
  39.  
  40.     for(int i=0;i<n;i++)
  41.     {
  42.         for(int j=0;j<n;j++)
  43.         {
  44.             visited[i][j]=false;
  45.         }
  46.     }
  47.     while(!q.empty())
  48.     {
  49.         int node=q.front();
  50.         q.pop();
  51.         int node1=q.front();
  52.         q.pop();
  53.         int dis=q.front();
  54.         q.pop();
  55.         if(node1==(n-1))
  56.         {
  57.             cout<<dis;
  58.             return 0;
  59.         }
  60.         for(int i=0;i<g[node1].size();i++)
  61.         {
  62.             int sosed=g[node1][i];
  63.             vector <int> mapa;
  64.             mapa.push_back(node);
  65.             mapa.push_back(node1);
  66.             mapa.push_back(sosed);
  67.             if(m[mapa]==false)
  68.             {
  69.                 if(!visited[node1][sosed])
  70.                 {
  71.                     q.push(node1);
  72.                     q.push(sosed);
  73.                     q.push(dis+1);
  74.                     visited[node1][sosed]=true;
  75.                 }
  76.             }
  77.         }
  78.     }
  79.     cout << "GRESHKA" << endl;
  80.     return 0;
  81. }
  82.  
  83.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement