fork download
copy 
  1.  #include <bits/stdc++.h>
  2.  
  3.  using namespace std ;
  4.  
  5.   #define sz(v) (int)v.size()
  6.   #define ll long long
  7.   #define all(v) v.begin() , v.end()
  8.   #define rall(v) v.rbegin() , v.rend()
  9.   #define pf push_front
  10.   #define pb push_back
  11.   #define fast FastInputOutput() ;
  12.   #define Clear( container , value ) memset( container , value , sizeof container )
  13.   #define PI acos( -1.0 )
  14.   #define c_b fflush(stdin);
  15.  
  16.   int dx[ ] = { 0 , 0 , -1 , 1 , 1 , -1 , 1 , 1 } ;
  17.   int dy[ ] = { -1 , 1 , 0 , 0 , 1 , -1 ,-1 ,-1 } ;
  18.  
  19.   void File_input( string pathIn , string pathOut ) {
  20.   freopen( pathIn.c_str() , "r", stdin ) ;
  21.   freopen( pathOut.c_str() , "w", stdout ) ;
  22.   }
  23.  
  24.   void FastInputOutput() {
  25.   ios_base :: sync_with_stdio( 0 ) ;
  26.   cin.tie( 0 ) ;
  27.   cout.tie( 0 ) ;
  28.   }
  29.  
  30.   const int N = 3e3 + 5 ;
  31.   int n , m , k , f , t , z ;
  32.   vector < int > adj[ N ] ;
  33.   int so_far[ N ] ;
  34.  map < pair < int , pair < int , int > > , bool > tribe ;
  35.   map < pair < int , int > , pair < int , int > > par ;
  36.  
  37.   void dijistra(){
  38.   par[ { 1 , so_far[ 1 ] } ] = { -1 , -1 } ;
  39.   queue < pair < int , int > > an ;
  40.   for( int i = 0 ; i < sz( adj[ 1 ] ) ; i++ ){
  41.   an.push( { adj[ 1 ][ i ] , 1 } ) ;
  42.   par[ { adj[ 1 ][ i ] , so_far[ adj[ 1 ][ i ] ] } ] ;
  43.   so_far[ adj[ 1 ][ i ] ]--;
  44.   so_far[ 1 ]-- ;
  45.   }
  46.   while( sz( an ) ){
  47.   int cur = an.front().first ;
  48.   int parent = an.front().second ;
  49.   an.pop() ;
  50.   if( cur == n ){
  51.  
  52.   pair < int , int > t ;
  53.   t = { n , sz( adj[ n ] ) } ;
  54.   vector < int > path ;
  55.   while( t.first != -1 && t.second != -1 ){
  56.   path.pb( t.first ) ;
  57.   cout << t.first << " " ;
  58.   t = par[ { t.first , t.second } ] ;
  59.   }
  60.  
  61.  
  62.   return;
  63.   }
  64.   for( auto node : adj[ cur ] ){
  65.   if( tribe[ { parent , { cur , node } } ] ) continue ;
  66.   if( so_far[ node ] ){
  67.   par[ { node , so_far[ node ] } ] = { parent , so_far[ parent ] } ;
  68.   so_far[ node ]-- ;
  69.   so_far[ parent ]-- ;
  70.   an.push( { node , cur } ) ;
  71.   }
  72.   }
  73.   }
  74.   cout << "-1" ;
  75.   }
  76.  
  77.   int main(){
  78.  
  79.   scanf("%d%d%d" , &n , &m , &k ) ;
  80.  
  81.   if( m == 1 ){
  82.   puts("-1") ;
  83.   return 0;
  84.   }
  85.  
  86.   while( m-- ){
  87.   scanf("%d%d" , &f , &t ) ;
  88.   so_far[ f ] += 1 ;
  89.   so_far[ t ] += 1 ;
  90.   adj[ f ].pb( t ) ;
  91.   adj[ t ].pb( f ) ;
  92.   }
  93.  
  94.  
  95.  
  96.   while( k-- ){
  97.   scanf("%d%d%d" , &f , &t , &z ) ;
  98.   tribe[ { f , { t , z } } ] = 1 ;
  99.   }
  100.  
  101.  
  102.  dijistra();
  103.  
  104.  
  105.  
  106.  
  107.  return 0 ;
  108. }
Success #stdin #stdout 0s 15320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/FpPDAY
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!