Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # include <iostream>
- # include <cmath>
- # include <vector>
- # include <algorithm>
- # include <string>
- # include <set>
- # include <map>
- # include <bitset>
- # include <queue>
- # include <iomanip>
- # include <string>
- # define FILE
- # define x first
- # define y second
- using namespace std;
- const int N = 1e5 + 100;
- int n, m, s, t, A, B;
- long long dist[N][2];
- vector < pair < int, int > > gr[N];
- set < pair < long long, pair < int, int > > > st;
- int main()
- {
- # ifdef FILE
- freopen( "travel.in", "r", stdin );
- freopen( "travel.out", "w", stdout );
- # endif // FILE
- # ifdef FILEs
- freopen( "input.txt", "r", stdin );
- freopen( "output.txt", "w", stdout );
- # endif // FILE
- ios_base::sync_with_stdio( false );
- cin >> n >> m;
- cin >> s >> t;
- for( int i = 1; i <= m; i ++ ){
- int a, b, c;
- cin >> a >> b >> c;
- gr[a].push_back( make_pair( c, b ) );
- gr[b].push_back( make_pair( c, a ) );
- }
- cin >> A >> B;
- for( int i = 1; i <= n; i ++ ){
- dist[i][0] = dist[i][1] = 1e18;
- }
- dist[s][0] = dist[s][1] = 0;
- st.insert( make_pair( 0, make_pair( s, 0 ) ) );
- st.insert( make_pair( 0, make_pair( s, 1 ) ) );
- while( st.empty() == false ){
- auto sp = *st.begin();
- st.erase( sp );
- long long d = sp.first;
- int v = sp.second.first;
- int tp = sp.second.second;
- for( auto to: gr[v] ){
- if( to.first >= B && dist[to.second][1] > d + to.first ){
- st.erase( make_pair( dist[to.second][1], make_pair( to.second, 1 )) );
- dist[to.second][1] = d+to.first;
- st.insert( make_pair( dist[to.second][1], make_pair( to.second, 1 )) );
- }
- if( tp == 0 ){
- if( to.first <= A && dist[to.second][0] > d + to.first ){
- st.erase( make_pair( dist[to.second][0], make_pair( to.second, 0 )) );
- dist[to.second][0] = d+to.first;
- st.insert( make_pair( dist[to.second][0], make_pair( to.second, 0 )) );
- }
- }
- }
- }
- long long mn = min( dist[t][0], dist[t][1] );
- if( mn == 1e18 ){
- cout << -1;
- }
- else{
- cout << mn;
- }
- # ifdef FILEs
- cout << endl << "------------------------";
- cout << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s. |";
- cout << endl << "------------------------";
- # endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement