Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define mp make_pair
- #define s second
- #define f first
- long long n,l=1,z,a,b,m,c,wys,h;//m-dlugosc, l-licznik, a-liczba wczytywanych dziur, b-miejsca dziur, counter
- vector <pair <long long, pair <long long, long long> > > p[100010];//przedzialy
- vector <pair <long long, long long> > g[100010];//graf
- vector <long long> ow;//ostatnie wyspy na poziomie
- priority_queue <pair <int, int> > kolejka;
- //priority_queue <pair <long double, long long>, vector <pair <long double, long long>>, greater <pair <long double, long long>>> kolejka;
- long long inf=674389374657836475ll;
- long long tab[3000010];
- void dijkstra()
- {
- tab[0]=0;
- for (long long i=1; i<=wys; ++i)
- {
- tab[i]=inf;
- }
- kolejka.push(mp(0,0));
- long long v,child, cena;
- while(!kolejka.empty())
- {
- v=kolejka.top().s;
- kolejka.pop();
- //cout<<v<<": ";
- for(long long i=0; i<(long long)g[v].size(); ++i)
- {
- child=g[v][i].s;
- cena=g[v][i].f;
- if (tab[child]>tab[v]+cena)
- {
- tab[child]=tab[v]+cena;
- kolejka.push(mp(tab[child], child));
- }
- //else cout<<"x "<<tab[v]+cena<<", "<<tab[child]<<", ";
- //cout<<child<<", "<<tab[child]<<", ";
- }
- //cout<<endl;
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin>>n>>m>>z;
- for(long long i=1; i<=n; ++i)
- {
- cin>>a>>b;
- wys+=a;
- wys++;
- p[i].push_back(mp(l,mp(1,b-1)));//kazdy przedzial to wierzcholek
- l++;//przedzialy ida na pale
- if (a>1)
- {
- for(long long j=1; j<a; ++j)
- {
- cin>>b;
- p[i].push_back(mp(l,mp(p[i][j-1].s.s+2,b-1)));//przedzial od ostatniej dziury do aktualnej
- g[l].push_back(mp(1, l-1));
- l++;
- }
- }
- p[i].push_back(mp(l,mp(p[i][a-1].s.s+2,m)));
- g[l].push_back(mp(1, l-1));
- g[0].push_back(mp(0,l));
- l++;
- }
- for(long long i=2; i<=n; ++i)
- {
- c=0;
- for(long long j=0; j<(long long)p[i].size(); ++j)
- {
- if (p[i-1][c].s.s<p[i][j].s.s) //schodzenie w dol z pierwszej wyspy u gory
- {
- g[p[i][j].f].push_back(mp(0,p[i-1][c].f));
- //cout<<c<<" "<<j<<", ";
- c++;
- }
- while(c<(long long)p[i-1].size())
- {
- if (p[i-1][c].s.f<=p[i][j].s.s+1 && p[i-1][c].s.f>p[i][j].s.f )
- {
- 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
- }
- else break;
- if (p[i-1][c].s.s<p[i][j].s.s)
- {
- g[p[i][j].f].push_back(mp(0,p[i-1][c].f));
- c++;//jak juz zejdziesz zmieniasz wyspe
- }
- else break;
- }
- }
- }
- /*for (int i=0; i<=wys; ++i)
- {
- for(int j=0; j<(int)g[i].size(); ++j) cout<<g[i][j].f<<" "<<g[i][j].s<<" ";
- cout<<endl;
- }*/
- dijkstra();
- for(long long i=0; i<z; ++i)
- {
- cin>>h;
- cout<<tab[p[h][0].f]<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement