Submission #498260

#	Time	Username	Problem	Language	Result	Execution time	Memory
498260		EliteCallsYou	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	57 ms	2204 KiB

merchant

# include <bits/stdc++.h>
using namespace std ;
//############################################################################
# define read(a)/**/for(int i=0;i<int(sizeof(a)/sizeof(a[0]));i++){cin>>a[i];}
# define print(x)/**/for(auto zx:x){cout<<zx<<' ';}
const char* tochar(string a){return a.c_str();}
void files(){freopen("hopscotch.in","r",stdin);freopen("hopscotch.out","w",stdout);}
void speed(){ios_base::sync_with_stdio(false);cin.tie(0);}
long long gcd(long long a,long long b){if(!b){return a;}a%=b;return gcd(b,a);}
long long lcm(long long a,long long b){return a /gcd(a,b) * b;}
//###########################################################################
const int N = 1e5 + 5 ;
const long long MOD = 1e9+7 ;
//###########################################################################
void hack(){}
//###########################################################################

# define node first
# define weight second
# define disstance first
# define cur_node second

int main(){
	/////////////////////////////////////////
	int n,m,k ; cin >> n >> m >> k ;
	int buy[n+1][k+1], sell[n+1][k+1] ;
	for ( int i = 1 ; i <= n ; i ++ ){
		for ( int j = 1 ; j <= k ; j ++ ){
			cin >> buy[i][j] >> sell[i][j] ;
		}
	}
	/////////////////////////////////////////
	vector < pair<int,int> > mp[n+1] ;
	for ( int i = 0 ; i < m ; i ++ ){
		int a,b,w ;
		cin >> a >> b >> w ;
		mp[a].push_back({b,w}) ;
	}
	/////////////////////////////////////////
	set < pair<int,int> > st ;
	map < int,int > dist ;
	// { disstance_needed, cur_node } ///
	st.insert({0,1}) ;
	while ( !st.empty() ){
		auto it = *st.begin() ; 
		st.erase(st.begin()) ;
		for ( auto child : mp[it.second] ){
			if ( it.first + child.second < dist[child.first] || !dist[child.first] ){
				st.erase({dist[child.first],child.first}) ;
				dist[child.first] = it.first + child.second ;
				st.insert({dist[child.first],child.first}) ;
			}
		}
	}
	int mx = 0 ;
	for ( int i = 2 ; i <= n ; i ++ ){
		for ( int j = 1 ; j <= k ; j ++ ){
			if ( buy[1][j] && sell[i][j] ){
				mx = max(mx, (sell[i][j]-buy[1][j])/dist[i] ) ;
			}
		}
	}
	cout << mx << '\n' ;
}

Compilation message (stderr)

merchant.cpp: In function 'void files()':
merchant.cpp:7:21: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | void files(){freopen("hopscotch.in","r",stdin);freopen("hopscotch.out","w",stdout);}
      |              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:7:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | void files(){freopen("hopscotch.in","r",stdin);freopen("hopscotch.out","w",stdout);}
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34