Advertisement
jkonefal

Untitled

Nov 22nd, 2020
262
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mp make_pair
  4. #define s second
  5. #define f first
  6. long long n,l=1,z,a,b,m,c,wys,h;//m-dlugosc, l-licznik, a-liczba wczytywanych dziur, b-miejsca dziur, counter
  7. vector <pair <long long, pair <long long, long long> > > p[100010];//przedzialy
  8. vector <pair <long long, long long> > g[100010];//graf
  9. vector <long long> ow;//ostatnie wyspy na poziomie
  10. priority_queue <pair <int, int> > kolejka;
  11. //priority_queue <pair <long double, long long>, vector <pair <long double, long long>>, greater <pair <long double, long long>>> kolejka;
  12. long long inf=674389374657836475ll;
  13. long long tab[3000010];
  14. void dijkstra()
  15. {
  16.     tab[0]=0;
  17.     for (long long i=1; i<=wys; ++i)
  18.     {
  19.         tab[i]=inf;
  20.     }
  21.     kolejka.push(mp(0,0));
  22.     long long v,child, cena;
  23.     while(!kolejka.empty())
  24.     {
  25.         v=kolejka.top().s;
  26.         kolejka.pop();
  27.         //cout<<v<<": ";
  28.         for(long long i=0; i<(long long)g[v].size(); ++i)
  29.         {
  30.             child=g[v][i].s;
  31.             cena=g[v][i].f;
  32.             if (tab[child]>tab[v]+cena)
  33.             {
  34.                 tab[child]=tab[v]+cena;
  35.                 kolejka.push(mp(tab[child], child));
  36.             }
  37.             //else cout<<"x "<<tab[v]+cena<<", "<<tab[child]<<", ";
  38.             //cout<<child<<", "<<tab[child]<<", ";
  39.         }
  40.         //cout<<endl;
  41.     }
  42. }
  43.  
  44. int main()
  45. {
  46.     ios_base::sync_with_stdio(0);
  47.     cin.tie(0);
  48.     cout.tie(0);
  49.     cin>>n>>m>>z;
  50.     for(long long i=1; i<=n; ++i)
  51.     {
  52.         cin>>a>>b;
  53.         wys+=a;
  54.         wys++;
  55.         p[i].push_back(mp(l,mp(1,b-1)));//kazdy przedzial to wierzcholek
  56.         l++;//przedzialy ida na pale
  57.         if (a>1)
  58.         {
  59.             for(long long j=1; j<a; ++j)
  60.             {
  61.                 cin>>b;
  62.                 p[i].push_back(mp(l,mp(p[i][j-1].s.s+2,b-1)));//przedzial od ostatniej dziury do aktualnej
  63.                 g[l].push_back(mp(1, l-1));
  64.                 l++;
  65.             }
  66.         }
  67.         p[i].push_back(mp(l,mp(p[i][a-1].s.s+2,m)));
  68.         g[l].push_back(mp(1, l-1));
  69.         g[0].push_back(mp(0,l));
  70.         l++;
  71.     }
  72.    
  73.    
  74.     for(long long i=2; i<=n; ++i)
  75.     {
  76.         c=0;
  77.         for(long long j=0; j<(long long)p[i].size(); ++j)
  78.         {
  79.             if (p[i-1][c].s.s<p[i][j].s.s) //schodzenie w dol z pierwszej wyspy u gory
  80.             {
  81.                 g[p[i][j].f].push_back(mp(0,p[i-1][c].f));
  82.                 //cout<<c<<" "<<j<<", ";
  83.                 c++;
  84.             }
  85.             while(c<(long long)p[i-1].size())
  86.             {
  87.                 if (p[i-1][c].s.f<=p[i][j].s.s+1 && p[i-1][c].s.f>p[i][j].s.f )
  88.                 {
  89.                 g[p[i-1][c].f].push_back(mp(1, p[i][j].f));//potem juz jest pattern dla gornej wyspy ze najpierw sie do niej wchdzi a potem schodzi
  90.                 }
  91.                 else break;
  92.                 if (p[i-1][c].s.s<p[i][j].s.s)
  93.                 {
  94.                     g[p[i][j].f].push_back(mp(0,p[i-1][c].f));
  95.                     c++;//jak juz zejdziesz zmieniasz wyspe
  96.                 }
  97.                 else break;
  98.             }
  99.         }
  100.     }
  101.     /*for (int i=0; i<=wys; ++i)
  102.     {
  103.         for(int j=0; j<(int)g[i].size(); ++j) cout<<g[i][j].f<<" "<<g[i][j].s<<" ";
  104.         cout<<endl;
  105.     }*/
  106.     dijkstra();
  107.     for(long long i=0; i<z; ++i)
  108.     {
  109.         cin>>h;
  110.         cout<<tab[p[h][0].f]<<"\n";
  111.     }
  112.    
  113. }
  114.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement