fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ull unsigned long long
  4. #define P (int)(1e9+7)
  5. #define ceil(x, y) (x%y==0? (x/y) : (x/y+1))
  6. #define FOR(i, N) for(int i = 0; i < N; ++i)
  7. #define FOR1(i, N) for(int i = 1; i <= N; ++i)
  8. #define vi vector <int>
  9. #define pii pair <int, int>
  10. #define pb push_back
  11. #define mp make_pair
  12. #define ff first
  13. #define ss second
  14. #define mset(a, v) memset(a, v, sizeof(a))
  15. #define all(v) v.begin(), v.end()
  16. #define INF 2e9
  17.  
  18. void BFS(vector<int> adj[], int s, int dist[], bool vis[]){
  19.  
  20.     queue<int> q;
  21.     q.push(s);
  22.     dist[s] = 0;
  23.     while(!q.empty()){
  24.         int v = q.front();
  25.         q.pop();
  26.  
  27.         if(vis[v]) continue;
  28.         vis[v] = true;
  29.         for(int i = 0; i < adj[v].size(); ++i){
  30.             if(dist[adj[v][i]] > dist[v] + 1 /*dist[adj[v][i]] == -1*/){
  31.                 q.push(adj[v][i]);
  32.                 dist[adj[v][i]] = dist[v] + 1;
  33.             }
  34.         }
  35.     }
  36. }
  37.  
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(NULL);
  41. 	int T;
  42. 	cin>>T;
  43. 	while(T-->0)
  44. 	{
  45.         vector<int> adj[101];
  46.         int dist[101]; fill(dist, dist+101, INF);
  47.         bool vis[101]; mset(vis, false);
  48.         for(int i = 1; i <= 100; i++){
  49.             for(int j = 1; j <= 6; j++){
  50.                 if(i+j <= 100) adj[i].pb(i+j);
  51.             }
  52.         }
  53.         int n; cin >> n; //ladders
  54.         while(n--){
  55.             int s, e; cin >> s >> e;
  56.             adj[s] = adj[e]; //make neighbours of end vertex as neighbours of start vertex, as start and end are essentially
  57.             //the same vertices as they have been connected by a ladder
  58.         }
  59.         int m; cin >> m; //snakes
  60.         while(m--) {
  61.             int s, e; cin >> s >> e;
  62.             adj[s] = adj[e];
  63.         }
  64.         BFS(adj, 1, dist, vis);
  65.         //FOR1(i, 100) cout  << i << ":" << dist[i] << " ";
  66.         cout << ((dist[100] == INF)? -1 : dist[100]);
  67. 	    cout<<'\n';
  68. 	}
  69. 	return 0;
  70. }
  71.  
Success #stdin #stdout 0s 4240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SgCeeL
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!