cosenza987

Untitled

Jul 24th, 2021
916
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<pair<int, int>> graf[512];
  6.  
  7. priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, std::greater<pair<int, pair<int, int>>>> q;
  8.  
  9. int cost[512];
  10.  
  11. int main() {
  12.     ios_base::sync_with_stdio(false);
  13.     cin.tie(0);
  14.     memset(cost, 0x3f3f3f3f, sizeof(cost));
  15.     int t, l, o, d, temp;
  16.     cin >> t >> l >> o >> d;
  17.     vector<bool> marca(t, false);
  18.     for(int i = 0; i < l; i++) {
  19.         int k, uk;
  20.         cin >> k >> uk;
  21.         if(uk == o) {
  22.             temp = i;
  23.         }
  24.         for(int j = 1; j < k; j++) {
  25.             int v;
  26.             cin >> v;
  27.             if(v == o) {
  28.                 temp = i;
  29.             }
  30.             graf[uk].push_back(make_pair(v, i));
  31.             graf[v].push_back(make_pair(uk, i));
  32.         }
  33.     }
  34.     cost[o] = 1;
  35.     q.push(make_pair(1, make_pair(o, temp)));
  36.     while(!q.empty()) {
  37.         pair<int, pair<int, int>> p = q.top();
  38.         q.pop();
  39.         int c = p.first, a = p.second.first;
  40.         if(!marca[a]) {
  41.             cost[a] = c;
  42.             marca[a] = true;
  43.             for(auto e : graf[a]) {
  44.                 int b = e.first, dd = e.second;
  45.                 if(!marca[b]) {
  46.                     if(dd == p.second.second) {
  47.                         q.push(make_pair(c, make_pair(b, dd)));
  48.                     } else {
  49.                         q.push(make_pair(c + 1, make_pair(b, dd)));
  50.                     }
  51.                 }
  52.             }
  53.         }
  54.     }
  55.     cout << cost[d] << "\n";
  56.     return 0;
  57. }
RAW Paste Data