Submission #549775

#	Time	Username	Problem	Language	Result	Execution time	Memory
549775		Pherokung	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	123 ms	4228 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,b[1005][105],s[1005][105],u,v,w,dis[105][105],val[105][105],cost[105][105],INF = 3e18;
bool valid(ll eff){
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) 
		cost[i][j] = dis[i][j] < INF ? (ll)(dis[i][j] * eff) - val[i][j] : INF;
		
	for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) 
		cost[i][j] = max(-INF,min(cost[i][j],cost[i][k] + cost[k][j]));
		
	for(int i=1;i<=n;i++) if(cost[i][i] <= 0) return true;
	return false;
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			scanf("%lld%lld",&b[j][i],&s[j][i]);
			if(b[j][i] == -1) b[j][i] = INF;
			if(s[j][i] == -1) s[j][i] = -INF;
		}
	}
	
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j] = INF;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		dis[u][v] = w;
	}
	
	for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) 
		dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int t=1;t<=k;t++) 
		val[i][j] = max(val[i][j], s[t][j] - b[t][i]);
	
	ll be = 1, ed = 1e9;
	while(be <= ed){
		ll mid = (be+ed)/2;
		if(valid(mid)) be = mid+1;
		else ed = mid-1;
	}
	printf("%lld",ed);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%lld%lld%lld",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:19:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |    scanf("%lld%lld",&b[j][i],&s[j][i]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%lld%lld%lld",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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