fork download
copy 
  1. #include<iostream>
  2. #include<queue>
  3.  
  4. using namespace std;
  5.  
  6. int d,n,m,z;
  7.  
  8. vector <pair<int,int> > Graf[25005];
  9.  
  10. priority_queue < pair<int,int> ,vector < pair<int,int> >,greater < pair<int,int> > > Qp;
  11.  
  12. bool odw[25005];
  13.  
  14. void BFS(int v)
  15. {
  16.     queue <int> Q;
  17.     odw[v] = true;
  18.     Q.push(v);
  19.     while(!Q.empty() || !Qp.empty())
  20.     {
  21.         while(!Q.empty())
  22.         {
  23.             int w = Q.front(),s = Graf[w].size();
  24.             cout<<w<<" "; Q.pop();
  25.             for(int i = 0;i < s; ++i)
  26.             {
  27.                 int u = Graf[w][i].second,k = Graf[w][i].first;
  28.                 if(!odw[u])
  29.                 {
  30.                     Qp.push(make_pair(k,u));
  31.                     odw[u] = true;
  32.                 }
  33.             }
  34.         }
  35.         while(!Qp.empty())
  36.         {
  37.             int t = Qp.top().second;
  38.             Q.push(t);
  39.             Qp.pop();
  40.         }
  41.     }
  42.     cout<<'\n';
  43. }
  44.  
  45. void czysc(int N)
  46. {
  47.     for(int i = 1;i <= N; ++i)
  48.     {
  49.         Graf[i].clear();
  50.         odw[i] = false;
  51.     }
  52. }
  53.  
  54. int main()
  55. {
  56.     ios_base::sync_with_stdio(0);
  57.     cin.tie(NULL);
  58.  
  59.     cin>>d;
  60.     for(int i = 0;i < d; ++i)
  61.     {
  62.         cin>>n>>m>>z;
  63.         for(int j = 0;j < m; ++j)
  64.         {
  65.             int a,b;
  66.             cin>>a>>b;
  67.             Graf[a].push_back(make_pair(j,b));
  68.         }
  69.         BFS(z);
  70.         czysc(n);
  71.     }
  72.     return 0;
  73. }
Success #stdin #stdout 0s 15848KB
comments (?)
stdin
copy 
3
6 8 5
1 3
3 5
4 6
5 2
3 4
2 6
3 6
2 4
5 4 1
4 5
2 3
1 2
1 4
6 10 5
1 3
3 5
4 6
5 2
5 3
3 4
2 6
3 6
2 4
5 3
stdout
copy 
5 2 6 4 
1 2 4 5 3 
5 2 3 6 4
https://ideone.com/mcI2Lf
language:
C++ (gcc 8.3)
created:
5 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!