Submission #205436

#	Time	Username	Problem	Language	Result	Execution time	Memory
205436		CaroLinda	Cities (BOI16_cities)	C++14	100 / 100	2483 ms	45308 KiB

cities

#include <bits/stdc++.h>

#define ll long long
#define debug 
#define all(x) x.begin(),x.end()

const int MAXN = 1e5+10 ;
const ll inf  = 1e18+10 ;

using namespace std ;

char c ;
inline void read(int &num)
{
	num = 0 ;
	c = getchar() ;
	for( ; ( c > 47 && c <58 ) ; c = getchar() )
		num = num*10 + c-48 ;
}

int N , K , M ; 
vector< pair<int,int> > adj[MAXN] ;
ll dist[100][MAXN] ;

int main()
{
	read(N) , read(K) , read(M) ;
	for(int i = 0 ; i < (1<<K) ; i++ ) 
 		for(int j = 1 ; j <= N ; j++ ) dist[i][j] = inf ;
	for(int i = 0 , x ; i < K ; i++ )
	{
		read(x) ;
		dist[ (1<<i) ][x] = 0 ;
	}
	for(int i = 0 ; i < M ; i++ )
	{
		int U , V , W ;
		read(U) , read(V) , read(W); 
		adj[U].push_back( make_pair(V,W) ) ;
		adj[V].push_back( make_pair(U,W) ) ;
 	}

 	for(int mask = 1 ; mask < (1<<K) ; mask ++ )
 	{

 		for(int submask = 1 ; submask <= mask>>1 ; submask ++  )
 		{

 			if( (submask&mask) != submask ) continue ;

 			int comp_submask = mask ^ submask ;

 			for(int i = 1 ; i <= N ; i++ ) 
 				dist[mask][i] = min( dist[mask][i] , dist[comp_submask][i] + dist[submask][i] ) ;

 		}

 		priority_queue< pair<ll,int> , vector< pair<ll,int> > , greater< pair<ll,int> > > fila ;

 		debug("com a mask %d -> " , mask ) ;

 		for(int i = 1 ; i <= N ; i++ )
 			if( dist[mask][i] != inf ) fila.push( make_pair( dist[mask][i] , i ) ) , debug("%d, " , i  ) ;
 		debug("\n\n") ;

 		while(!fila.empty())
 		{

 			ll d = fila.top().first ;
 			int curr = fila.top().second ;

 			debug("Processando %d\n" , curr );

 			fila.pop() ;

 			if( d != dist[mask][curr] ) continue ;

 			for(auto viz : adj[curr] )
 			{


 				ll W = viz.second + d ;

 				if( W >= dist[mask][viz.first] ) continue ;

 				dist[mask][viz.first] = W ;

 				fila.push( make_pair( W, viz.first ) ) ;

 			}


 		}

 	}

 	printf("%lld\n", *min_element( dist[ (1<<K)-1 ]+1, dist[ (1<<K)-1 ] + N + 1 ) ) ;

}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:60:32: warning: left operand of comma operator has no effect [-Wunused-value]
    debug("com a mask %d -> " , mask ) ;
                                ^~~~
cities.cpp:63:93: warning: left operand of comma operator has no effect [-Wunused-value]
     if( dist[mask][i] != inf ) fila.push( make_pair( dist[mask][i] , i ) ) , debug("%d, " , i  ) ;
                                                                                             ^
cities.cpp:64:18: warning: statement has no effect [-Wunused-value]
    debug("\n\n") ;
                  ^
cities.cpp:72:32: warning: left operand of comma operator has no effect [-Wunused-value]
     debug("Processando %d\n" , curr );
                                ^~~~

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26