Advertisement
jkonefal

Untitled

Nov 20th, 2020
274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.51 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. int 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 <int, pair <int, int> > > p[100010];//przedzialy
  8. vector <pair <int, int> > g[100010];//graf
  9. vector <int> 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=674389374657836475;
  13. long long tab[3000010];
  14. void dijkstra(int x)
  15. {
  16.     for (int i=1; i<=wys; ++i)
  17.     {
  18.         tab[i]=inf;
  19.     }
  20.     kolejka.push(mp(0,0));
  21.     int v,child, cena;
  22.     while(!kolejka.empty())
  23.     {
  24.         v=kolejka.top().second;
  25.         kolejka.pop();
  26.         for(int i=0; i<(int)g[v].size(); ++i)
  27.         {
  28.             child=g[v][i].second;
  29.             cena=g[v][i].first;
  30.             if (tab[child]>tab[v]+cena)
  31.             {
  32.                 tab[child]=tab[v]+cena;
  33.                 kolejka.push(mp(tab[child], child));
  34.             }
  35.            
  36.         }
  37.     }
  38. }
  39.  
  40. int main()
  41. {
  42.     ios_base::sync_with_stdio(0);
  43.     cin.tie(0);
  44.     cout.tie(0);
  45.     cin>>n>>m>>z;
  46.     for(int i=1; i<=n; ++i)
  47.     {
  48.         cin>>a>>b;
  49.         wys+=a;
  50.         wys++;
  51.         p[i].push_back(mp(l,mp(1,b-1)));//kazdy przedzial to wierzcholek
  52.         l++;//przedzialy ida na pale
  53.         if (a>1)
  54.         {
  55.             for(int j=1; j<a; ++j)
  56.             {
  57.                 cin>>b;
  58.                 p[i].push_back(mp(l,mp(p[i][j-1].s.s+2,b-1)));//przedzial od ostatniej dziury do aktualnej
  59.                 g[l].push_back(mp(1, l-1));
  60.                 l++;
  61.             }
  62.         }
  63.         p[i].push_back(mp(l,mp(p[i][a-1].s.s+2,m)));
  64.         g[l].push_back(mp(1, l-1));
  65.         g[0].push_back(mp(0,l));
  66.         l++;
  67.     }
  68.    
  69.    
  70.     for(int i=2; i<=n; ++i)
  71.     {
  72.         c=0;
  73.         for(int j=0; j<(int)p[i].size(); ++j)
  74.         {
  75.             if (p[i-1][c].s.s<p[i][j].s.s) //schodzenie w dol z pierwszej wyspy u gory
  76.             {
  77.                 g[p[i][j].f].push_back(mp(0,p[i-1][c].f));
  78.                 //cout<<c<<" "<<j<<", ";
  79.                 c++;
  80.             }
  81.             while(c<(int)p[i-1].size())
  82.             {
  83.                 if (p[i-1][c].s.f<=p[i][j].s.s+1 && p[i-1][c].s.f>p[i][j].s.f )
  84.                 {
  85.                 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
  86.                 }
  87.                 else break;
  88.                 if (p[i-1][c].s.s<p[i][j].s.s)
  89.                 {
  90.                     g[p[i][j].f].push_back(mp(0,p[i-1][c].f));
  91.                     c++;//jak juz zejdziesz zmieniasz wyspe
  92.                 }
  93.                 else break;
  94.             }
  95.         }
  96.     }
  97.     for (int i=0; i<=wys; ++i)
  98.     {
  99.         for(int j=0; j<(int)g[i].size(); ++j) cout<<g[i][j].s<<" ";
  100.         cout<<endl;
  101.     }
  102.     dijkstra(0);
  103.     for(int i=0; i<z; ++i)
  104.     {
  105.         cin>>h;
  106.         cout<<tab[p[h][0].f]<<endl;
  107.     }
  108.    
  109. }          
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement