BoxerTC

Untitled

Mar 5th, 2015
297
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.81 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sc( x ) scanf( "%d" , &x )
  5. #define REP( i , n ) for( int i = 0 ; i < n ; ++i )
  6. #define clr( t , val ) memset( t , val , sizeof( t ) )
  7.  
  8. #define pb push_back
  9. #define all( v ) v.begin() , v.end()
  10. #define SZ( v ) ((int)(v).size())
  11.  
  12. #define fi first
  13. #define se second
  14. #define mp make_pair
  15.  
  16. #define N 10000
  17. #define M 10000
  18. #define INF 100000000000000000LL
  19.  
  20. typedef pair< int , int > pii;
  21. typedef vector< int > vi;
  22. typedef vector< vi > vvi;
  23. typedef vector< pii > vpii;
  24. typedef long long ll;
  25. typedef vector< ll > vll;
  26.  
  27. int orig[ M + 5 ] , dest[ M + 5 ] , peso[ M + 5 ];
  28. bool used[ N + 5 ];
  29.  
  30. vi G[ N + 5 ] ;
  31. vll C[ N + 5 ];
  32. int m , n ;
  33. void add( int u , int v , ll w ){
  34.     G[ u ].pb( v );
  35.     C[ u ].pb( w );
  36. }
  37. struct Node{
  38.     int id ;
  39.     ll dist;
  40.     Node( int id , ll dist ) : id( id ) , dist( dist ) {}
  41. };
  42. bool operator < ( const Node &a , const Node &b ){ return a.dist > b.dist; }
  43.  
  44. vll dijkstra( int s ){
  45.     vll dist( n , INF );
  46.     priority_queue< Node > Q;
  47.     dist[ s ] = 0;
  48.     Q.push( Node( s , 0 ) );
  49.     while( !Q.empty() ){
  50.         Node U = Q.top() ; Q.pop();
  51.         int u = U.id ;
  52.         REP( i , SZ( G[ u ] ) ){
  53.             int v = G[ u ][ i ];
  54.             ll w = C[ u ][ i ];
  55.             if( dist[ u ] + w < dist[ v ] ){
  56.                 dist[ v ] = dist[ u ] + w;
  57.                 Q.push( Node( v , dist[ v ] ) );
  58.             }
  59.         }
  60.     }
  61.     return dist;
  62. }
  63. /*
  64. int id[ N + 5 ];
  65. int Find( int x ){ return id[ x ] = (id[ x ] == x ? x : Find( id[ x ] ));}
  66. void Union( int a , int b ){
  67.     int pa = Find( a ) , pb = Find( b );
  68.     if( pa != pb ) id[ pa ] = pb;
  69. }
  70. */
  71. bool f( ll x , int s , int t ){
  72.     REP( i , N ) G[ i ].clear() , C[ i ].clear();
  73.     REP( i , m ){
  74.         int u = orig[ i ] , v = dest[ i ] ; ll w = peso[ i ];
  75.         w += x;
  76.         add( u , v , w );
  77.         add( v , u , w );
  78.     }
  79.     vll ds = dijkstra( s );
  80.     vll dt = dijkstra( t );
  81.     ll di = ds[ t ];
  82.     REP( i , m ){
  83.         int u = orig[ i ] , v = dest[ i ] ; ll w = peso[ i ];
  84.         w += x;
  85.         if( ds[ u ] + w + dt[ v ] == di || ds[ v ] + w + dt[ u ] == di ){
  86.             if( !used[ u ] || !used[ v ] ) return 0;
  87.         }
  88.     }
  89.     return 1;
  90. }
  91. int main(){
  92.     int s , t;
  93.     while( sc( n ) == 1 ){
  94.         sc( m ) , sc( s ) , sc( t );
  95.         s -- , t --;
  96.         REP( i , m ){
  97.             int u , v , w;
  98.             sc( u ) , sc( v ) , sc( w );
  99.             u -- , v --;
  100.             orig[ i ] = u , dest[ i ] = v , peso[ i ] = w;
  101.         }  
  102.         int len;
  103.         sc( len );
  104.         clr( used , 0 );
  105.         REP( i , len ){
  106.             int u ;
  107.             sc( u );
  108.             u --;
  109.             used[ u ] = 1;
  110.         }
  111.         ll lo = 1 , hi = 100000000000000LL;
  112.         if( f( hi , s , t ) ){
  113.             cout << "Infinity\n";
  114.             continue;
  115.         }
  116.         if( !f( lo , s , t ) ){
  117.             cout << "Impossible\n";
  118.             continue;
  119.         }
  120.  
  121.         while( hi - lo > 1 ){
  122.             ll med = (lo + hi)>>1LL;
  123.             if( f( med , s , t ) ) lo = med;
  124.             else hi = med;
  125.         }
  126.         cout << lo << '\n';
  127.     }
  128. }
Advertisement
Add Comment
Please, Sign In to add comment