Guest User

Untitled

a guest
Jan 17th, 2019
66
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<fstream>
  3. #include<cstring>
  4. #include<vector>
  5.  
  6. using namespace std;
  7.  
  8. const int max_n=10e5;
  9. int start,konec,tstart,tend,prib[max_n][2],que[max_n],n,m,a,b,tain,taout;
  10. int head=0,tail=1,next,now;
  11. int ans, mans[max_n];
  12.  
  13.  
  14.  
  15. vector< vector<int> > graph;
  16.  
  17. vector< vector<int> > grin;
  18.  
  19. vector< vector<int> > grout;
  20.  
  21. void BFS(),dop();
  22.  
  23. void Input()
  24. {
  25.  
  26. cin >> n;
  27. cin >> m;
  28. graph.resize(n+1);
  29. grin.resize(n+1);
  30. grout.resize(n+1);
  31.  
  32. for(int i=0;i<m;i++)
  33. {
  34. cin >> a;
  35. cin >> b;
  36.  
  37. graph[a].push_back(b);
  38.  
  39. cin >> tain >> taout;
  40.  
  41. grin[a].push_back(tain);
  42. grout[a].push_back(taout);
  43. }
  44.  
  45. cin >> start >> konec >> tstart >> tend;
  46.  
  47.  
  48. }
  49.  
  50. void Solution()
  51. {
  52. for(int i=0;i<n;i++)
  53. prib[i][0]=(1e6)+1;
  54. prib[start][1]=-1;
  55. BFS();
  56.  
  57.  
  58. }
  59.  
  60. void Output()
  61. {
  62. int kol=0;
  63. cout<<ans;
  64. //for(int i= ans ;i != -1;i=prib[i][1] )
  65. // mans[kol++]=i;
  66.  
  67. /* cout<<kol<<"\n";
  68. for(int i=kol;i>=0;i--)
  69. {
  70. cout<<mans[i]<<" ";
  71. }
  72. cout<<"\n";*/
  73. }
  74.  
  75. int main()
  76. {
  77. Input();
  78. Solution();
  79. Output();
  80.  
  81. return 0;
  82. }
  83.  
  84. void BFS()
  85. {
  86.  
  87. que[0]=start;
  88. prib[start][0]=tstart;
  89. while( head < tail )
  90. {
  91.  
  92.  
  93.  
  94. if(now == konec && tend >= prib[now][0]) { ans=head ; return; }
  95.  
  96. now=que[head];
  97. for(int i = 0;i < graph[now].size();i++)
  98. {
  99. next=graph[now][i];
  100. if(prib[now][0] <= grin[now][i] ) {
  101.  
  102. if( prib[next][0] > grout[now][i] ){
  103. que[tail++] = graph[now][i];
  104. prib[next][0] = grout[now][i];
  105. prib[next][1] = now;
  106. dop();
  107. }
  108. if( prib[graph[next][i]][0] == (1e6)+1){que[tail++]; prib[graph[next][i]][0]=grout[now][i]; prib[graph[next][i]][1]=now; }
  109. }
  110. }
  111. ///
  112.  
  113.  
  114. head++;
  115. }
  116. }
  117.  
  118. void dop()
  119. {
  120. for(int i=0;i<graph[next].size();i++ )
  121. {
  122. if( prib[graph[next][i]][0] ==(1e6)+1 && prib[next][0] <= grin[next][i] ) {
  123. que[tail++];
  124. prib[graph[next][i]][1]=next;
  125. prib[graph[next][i]][0]=grout[next][i];
  126.  
  127. }
  128. }
  129. }
RAW Paste Data