liartie

Untitled

Nov 3rd, 2020
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #define int long long
  6.  
  7. using namespace std;
  8.  
  9. const int INF = 1e9;
  10.  
  11. map <pair <int, int>, vector <pair <pair <int, int>, int> > > g;
  12. map <pair <int, int>, bool> is_hole;
  13. map <pair <int, int>, int> dist;
  14. set <pair <int, pair <int, int> > > q;
  15.  
  16. ostream &operator << (ostream &out, pair <int, int> &p){
  17.     out<<p.first<<" "<<p.second;
  18.     return out;
  19. }
  20.  
  21. signed main(){
  22.     int n, m, z;
  23.     cin>>n>>m>>z;
  24.     for(int i = 0; i < n; i++){
  25.         int k, prev = -1;
  26.         cin>>k;
  27.         for(int j = 0; j < k; j++){
  28.             int x;
  29.             cin>>x;
  30.             x--;
  31.             is_hole[{i, x}] = true;
  32.             if(j == 0){
  33.                 g[{i, 0}].push_back({{i, x}, 0});
  34.             }
  35.             else{
  36.                 g[{i, prev}].push_back({{i, x}, 1});
  37.             }
  38.             if(i < n - 1){
  39.                 g[{i, x}].push_back({{i + 1, x}, 0});
  40.                 g[{i + 1, x}].push_back({{i, x}, 0});
  41.             }
  42.             prev = x;
  43.         }
  44.         if(prev == -1){
  45.             g[{i, 0}].push_back({{i, m}, 0});
  46.         }
  47.         else{
  48.             g[{i, prev}].push_back({{i, m}, 1});
  49.         }
  50.         g[{i, m}].push_back({{i, m}, INF});
  51.     }
  52.    
  53.     for(auto it = g.begin(); it != g.end(); it++){
  54.         if(it->second.size() == 1 && it->second[0].first.first == it->first.first - 1 && it->second[0].first.second == it->first.second){
  55.             auto it2 = it, it3 = it;
  56.             it2++;
  57.             it3--;
  58.             g[{it->first}].push_back({{it2->first}, 0});
  59. //          cout<<"Adding extra: \n";
  60. //          cout<<"From "<<it3->first.first + 1<<" "<<it3->first.second + 1<<" to "<<it->first.first + 1<<" "<<it->first.second + 1<<"\n";
  61. //          cout<<"From "<<it->first.first + 1<<" "<<it->first.second + 1<<" to "<<it2->first.first + 1<<" "<<it2->first.second + 1<<"\n";
  62.             if(is_hole[{it3->first}]){
  63.                 g[{it3->first}].push_back({{it->first}, 1});
  64.             }
  65.             else{
  66.                 g[{it3->first}].push_back({{it->first}, 0});
  67.             }
  68.         }
  69.     }
  70.    
  71. //  for(auto it = g.begin(); it != g.end(); it++){
  72. //      cout<<"From "<<it->first.first + 1<<" "<<it->first.second + 1<<":\n";
  73. //      for(int i = 0; i < it->second.size(); i++){
  74. //          cout<<it->second[i].first.first + 1<<" "<<it->second[i].first.second + 1<<" for "<<it->second[i].second<<"\n";
  75. //      }
  76. //      cout<<"\n";
  77. //  }
  78.    
  79.     while(z--){
  80.         int start, ans = INF;
  81.         cin>>start;
  82.         start--;
  83.         dist.clear();
  84.         dist[{start, 0}] = 0;
  85.         q.insert({0, {start, 0}});
  86.         while(q.size()){
  87.             pair <int, int> v = (*q.begin()).second;
  88.             if(v.second == m){
  89.                 ans = min(ans, dist[v]);
  90.             }
  91.             q.erase(q.begin());
  92.             for(int i = 0; i < g[v].size(); i++){
  93.                 int cost = g[v][i].second;
  94.                 pair <int, int> u = g[v][i].first;
  95.                 if(dist.find(u) == dist.end() || dist[u] > dist[v] + cost){
  96.                     q.erase({dist[u], u});
  97.                     dist[u] = dist[v] + cost;
  98.                     q.insert({dist[u], u});
  99.                 }
  100.             }
  101.         }
  102.         cout<<ans<<"\n";
  103.     }
  104.    
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment