Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define sc( x ) scanf( "%d" , &x )
- #define REP( i , n ) for( int i = 0 ; i < n ; ++i )
- #define clr( t , val ) memset( t , val , sizeof( t ) )
- #define pb push_back
- #define all( v ) v.begin() , v.end()
- #define SZ( v ) ((int)(v).size())
- #define fi first
- #define se second
- #define mp make_pair
- #define N 10000
- #define M 10000
- #define INF 100000000000000000LL
- typedef pair< int , int > pii;
- typedef vector< int > vi;
- typedef vector< vi > vvi;
- typedef vector< pii > vpii;
- typedef long long ll;
- typedef vector< ll > vll;
- int orig[ M + 5 ] , dest[ M + 5 ] , peso[ M + 5 ];
- bool used[ N + 5 ];
- vi G[ N + 5 ] ;
- vll C[ N + 5 ];
- int m , n ;
- void add( int u , int v , ll w ){
- G[ u ].pb( v );
- C[ u ].pb( w );
- }
- struct Node{
- int id ;
- ll dist;
- Node( int id , ll dist ) : id( id ) , dist( dist ) {}
- };
- bool operator < ( const Node &a , const Node &b ){ return a.dist > b.dist; }
- vll dijkstra( int s ){
- vll dist( n , INF );
- priority_queue< Node > Q;
- dist[ s ] = 0;
- Q.push( Node( s , 0 ) );
- while( !Q.empty() ){
- Node U = Q.top() ; Q.pop();
- int u = U.id ;
- REP( i , SZ( G[ u ] ) ){
- int v = G[ u ][ i ];
- ll w = C[ u ][ i ];
- if( dist[ u ] + w < dist[ v ] ){
- dist[ v ] = dist[ u ] + w;
- Q.push( Node( v , dist[ v ] ) );
- }
- }
- }
- return dist;
- }
- /*
- int id[ N + 5 ];
- int Find( int x ){ return id[ x ] = (id[ x ] == x ? x : Find( id[ x ] ));}
- void Union( int a , int b ){
- int pa = Find( a ) , pb = Find( b );
- if( pa != pb ) id[ pa ] = pb;
- }
- */
- bool f( ll x , int s , int t ){
- REP( i , N ) G[ i ].clear() , C[ i ].clear();
- REP( i , m ){
- int u = orig[ i ] , v = dest[ i ] ; ll w = peso[ i ];
- w += x;
- add( u , v , w );
- add( v , u , w );
- }
- vll ds = dijkstra( s );
- vll dt = dijkstra( t );
- ll di = ds[ t ];
- REP( i , m ){
- int u = orig[ i ] , v = dest[ i ] ; ll w = peso[ i ];
- w += x;
- if( ds[ u ] + w + dt[ v ] == di || ds[ v ] + w + dt[ u ] == di ){
- if( !used[ u ] || !used[ v ] ) return 0;
- }
- }
- return 1;
- }
- int main(){
- int s , t;
- while( sc( n ) == 1 ){
- sc( m ) , sc( s ) , sc( t );
- s -- , t --;
- REP( i , m ){
- int u , v , w;
- sc( u ) , sc( v ) , sc( w );
- u -- , v --;
- orig[ i ] = u , dest[ i ] = v , peso[ i ] = w;
- }
- int len;
- sc( len );
- clr( used , 0 );
- REP( i , len ){
- int u ;
- sc( u );
- u --;
- used[ u ] = 1;
- }
- ll lo = 1 , hi = 100000000000000LL;
- if( f( hi , s , t ) ){
- cout << "Infinity\n";
- continue;
- }
- if( !f( lo , s , t ) ){
- cout << "Impossible\n";
- continue;
- }
- while( hi - lo > 1 ){
- ll med = (lo + hi)>>1LL;
- if( f( med , s , t ) ) lo = med;
- else hi = med;
- }
- cout << lo << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment