oj.uz

Submission #205436

# Submission time Handle Problem Language Result Execution time Memory
205436 2020-02-29T00:23:13 Z CaroLinda Cities (BOI16_cities) C++14
100 / 100
 2483 ms 45308 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 7 ms 2808 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 26004 KB Output is correct
2 Correct 571 ms 25748 KB Output is correct
3 Correct 362 ms 17900 KB Output is correct
4 Correct 66 ms 10804 KB Output is correct
5 Correct 315 ms 20628 KB Output is correct
6 Correct 60 ms 10744 KB Output is correct
7 Correct 10 ms 2936 KB Output is correct
8 Correct 8 ms 2808 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3064 KB Output is correct
2 Correct 11 ms 3064 KB Output is correct
3 Correct 9 ms 2936 KB Output is correct
4 Correct 9 ms 2936 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 32116 KB Output is correct
2 Correct 1173 ms 32096 KB Output is correct
3 Correct 767 ms 24216 KB Output is correct
4 Correct 630 ms 22664 KB Output is correct
5 Correct 173 ms 13700 KB Output is correct
6 Correct 78 ms 12536 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2483 ms 45308 KB Output is correct
2 Correct 2427 ms 45012 KB Output is correct
3 Correct 2357 ms 44680 KB Output is correct
4 Correct 1575 ms 36804 KB Output is correct
5 Correct 1215 ms 28808 KB Output is correct
6 Correct 255 ms 14972 KB Output is correct
7 Correct 84 ms 12700 KB Output is correct