Advertisement
Josif_tepe

Untitled

Feb 6th, 2024
857
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <map>
  6. #include <fstream>
  7. #include <set>
  8. using namespace std;
  9. typedef long long ll;
  10. const int maxn = 3005;
  11. vector<int> graph[maxn];
  12. bool visited[maxn][maxn];
  13. int main() {
  14.     ios_base::sync_with_stdio(false);
  15.     int n, m;
  16.     cin >> n >> m;
  17.    
  18.     for(int i = 0; i < m; i++) {
  19.         int a, b;
  20.         cin >> a >> b;
  21.         graph[a].push_back(b);
  22.         graph[b].push_back(a);
  23.     }
  24.     int k;
  25.     cin >> k;
  26.     map<vector<int>, bool> triplets;
  27.     for(int i = 0; i < k; i++) {
  28.         int a, b, c;
  29.         cin >> a >> b >> c;
  30.         triplets[{a, b, c}] = true;
  31.     }
  32.    
  33.     queue<int> q;
  34.     q.push(0);
  35.     q.push(-1);
  36.     q.push(0);
  37.     while(!q.empty()) {
  38.         int current_node = q.front(); q.pop();
  39.         int prev_node = q.front(); q.pop();
  40.         int cekor = q.front(); q.pop();
  41.        
  42.         if(current_node == n - 1) {
  43.             cout << cekor << endl;
  44.             return 0;
  45.         }
  46.         for(int i = 0; i < (int) graph[current_node].size(); i++) {
  47.             int neighbour = graph[current_node][i];
  48.             if(!triplets[{prev_node, current_node, neighbour}] and !visited[current_node][neighbour]) {
  49.                 visited[current_node][neighbour] = true;
  50.                 q.push(neighbour);
  51.                 q.push(current_node);
  52.                 q.push(cekor + 1);
  53.             }
  54.            
  55.         }
  56.     }
  57.     cout << "GRESHKA" << endl;
  58.    
  59.     return 0;
  60. }
  61.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement