Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <set>
- #define int long long
- using namespace std;
- const int INF = 1e9;
- map <pair <int, int>, vector <pair <pair <int, int>, int> > > g;
- map <pair <int, int>, bool> is_hole;
- map <pair <int, int>, int> dist;
- set <pair <int, pair <int, int> > > q;
- ostream &operator << (ostream &out, pair <int, int> &p){
- out<<p.first<<" "<<p.second;
- return out;
- }
- signed main(){
- int n, m, z;
- cin>>n>>m>>z;
- for(int i = 0; i < n; i++){
- int k, prev = -1;
- cin>>k;
- for(int j = 0; j < k; j++){
- int x;
- cin>>x;
- x--;
- is_hole[{i, x}] = true;
- if(j == 0){
- g[{i, 0}].push_back({{i, x}, 0});
- }
- else{
- g[{i, prev}].push_back({{i, x}, 1});
- }
- if(i < n - 1){
- g[{i, x}].push_back({{i + 1, x}, 0});
- g[{i + 1, x}].push_back({{i, x}, 0});
- }
- prev = x;
- }
- if(prev == -1){
- g[{i, 0}].push_back({{i, m}, 0});
- }
- else{
- g[{i, prev}].push_back({{i, m}, 1});
- }
- g[{i, m}].push_back({{i, m}, INF});
- }
- for(auto it = g.begin(); it != g.end(); it++){
- if(it->second.size() == 1 && it->second[0].first.first == it->first.first - 1 && it->second[0].first.second == it->first.second){
- auto it2 = it, it3 = it;
- it2++;
- it3--;
- g[{it->first}].push_back({{it2->first}, 0});
- // cout<<"Adding extra: \n";
- // cout<<"From "<<it3->first.first + 1<<" "<<it3->first.second + 1<<" to "<<it->first.first + 1<<" "<<it->first.second + 1<<"\n";
- // cout<<"From "<<it->first.first + 1<<" "<<it->first.second + 1<<" to "<<it2->first.first + 1<<" "<<it2->first.second + 1<<"\n";
- if(is_hole[{it3->first}]){
- g[{it3->first}].push_back({{it->first}, 1});
- }
- else{
- g[{it3->first}].push_back({{it->first}, 0});
- }
- }
- }
- // for(auto it = g.begin(); it != g.end(); it++){
- // cout<<"From "<<it->first.first + 1<<" "<<it->first.second + 1<<":\n";
- // for(int i = 0; i < it->second.size(); i++){
- // cout<<it->second[i].first.first + 1<<" "<<it->second[i].first.second + 1<<" for "<<it->second[i].second<<"\n";
- // }
- // cout<<"\n";
- // }
- while(z--){
- int start, ans = INF;
- cin>>start;
- start--;
- dist.clear();
- dist[{start, 0}] = 0;
- q.insert({0, {start, 0}});
- while(q.size()){
- pair <int, int> v = (*q.begin()).second;
- if(v.second == m){
- ans = min(ans, dist[v]);
- }
- q.erase(q.begin());
- for(int i = 0; i < g[v].size(); i++){
- int cost = g[v][i].second;
- pair <int, int> u = g[v][i].first;
- if(dist.find(u) == dist.end() || dist[u] > dist[v] + cost){
- q.erase({dist[u], u});
- dist[u] = dist[v] + cost;
- q.insert({dist[u], u});
- }
- }
- }
- cout<<ans<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment