Advertisement
Guest User

Untitled

a guest
Oct 19th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.53 KB | None | 0 0
  1. # include <iostream>
  2. # include <cmath>
  3. # include <vector>
  4. # include <algorithm>
  5. # include <string>
  6. # include <set>
  7. # include <map>
  8. # include <bitset>
  9. # include <queue>
  10. # include <iomanip>
  11. # include <string>
  12.  
  13. # define FILE
  14. # define x first
  15. # define y second
  16. using namespace std;
  17.  
  18. const int N = 1e5 + 100;
  19.  
  20. int n, m, s, t, A, B;
  21. long long dist[N][2];
  22. vector < pair < int, int > > gr[N];
  23. set < pair < long long, pair < int, int > > > st;
  24.  
  25. int main()
  26. {
  27.     # ifdef FILE
  28.         freopen( "travel.in", "r", stdin );
  29.         freopen( "travel.out", "w", stdout );
  30.     # endif // FILE
  31.  
  32.     # ifdef FILEs
  33.         freopen( "input.txt", "r", stdin );
  34.         freopen( "output.txt", "w", stdout );
  35.     # endif // FILE
  36.     ios_base::sync_with_stdio( false );
  37.  
  38.     cin >> n >> m;
  39.     cin >> s >> t;
  40.     for( int i = 1; i <= m; i ++ ){
  41.         int a, b, c;
  42.         cin >> a >> b >> c;
  43.         gr[a].push_back( make_pair( c, b ) );
  44.         gr[b].push_back( make_pair( c, a ) );
  45.     }
  46.     cin >> A >> B;
  47.     for( int i = 1; i <= n; i ++ ){
  48.         dist[i][0] = dist[i][1] = 1e18;
  49.     }
  50.     dist[s][0] = dist[s][1] = 0;
  51.     st.insert( make_pair( 0, make_pair( s, 0 ) ) );
  52.     st.insert( make_pair( 0, make_pair( s, 1 ) ) );
  53.  
  54.     while( st.empty() == false ){
  55.         auto sp = *st.begin();
  56.         st.erase( sp );
  57.         long long d = sp.first;
  58.         int v = sp.second.first;
  59.         int tp = sp.second.second;
  60.         for( auto to: gr[v] ){
  61.             if( to.first >= B && dist[to.second][1] > d + to.first ){
  62.                     st.erase( make_pair( dist[to.second][1], make_pair( to.second, 1 )) );
  63.                     dist[to.second][1] = d+to.first;
  64.                     st.insert( make_pair( dist[to.second][1], make_pair( to.second, 1 )) );
  65.                 }
  66.             if( tp == 0 ){
  67.                 if( to.first <= A && dist[to.second][0] > d + to.first ){
  68.                     st.erase( make_pair( dist[to.second][0], make_pair( to.second, 0 )) );
  69.                     dist[to.second][0] = d+to.first;
  70.                     st.insert( make_pair( dist[to.second][0], make_pair( to.second, 0 )) );
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     long long mn = min( dist[t][0], dist[t][1] );
  76.     if( mn == 1e18 ){
  77.         cout << -1;
  78.     }
  79.     else{
  80.         cout << mn;
  81.     }
  82.     # ifdef FILEs
  83.         cout << endl << "------------------------";
  84.         cout << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s. |";
  85.         cout << endl << "------------------------";
  86.     # endif
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement