SHARE
TWEET

Untitled

a guest Jan 17th, 2019 59 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top