Submission #49745

#	Time	Username	Problem	Language	Result	Execution time	Memory
49745		top34051	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	122 ms	2168 KiB

merchant

#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;

int n,m,k;
long long a[105][1005], b[105][1005];
long long profit[105][105], dist[105][105];
long long ok[105][105];

bool check(long long val) {
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			if(profit[i][j]==-inf || dist[i][j]==inf) ok[i][j] = -inf;
			else ok[i][j] = profit[i][j] - val * dist[i][j];
		}
	}
	for(int x=1;x<=n;x++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				ok[i][j] = max(ok[i][j], ok[i][x] + ok[x][j]);
			}
		}
	}
	for(int i=1;i<=n;i++) if(ok[i][i]>=0) return 1;
	return 0;
}

int main() {
	int i,j,x,y;
	long long val;

	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=k;j++) {
			scanf("%lld%lld",&a[i][j],&b[i][j]);
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			dist[i][j] = inf;
			profit[i][j] = -inf;
		}
	}
	for(int i=1;i<=m;i++) {
		scanf("%d%d%lld",&x,&y,&val);
		dist[x][y] = min(dist[x][y], val);
		dist[y][x] = min(dist[y][x], val);
	}

	//get dist[x][y]
	for(int x=1;x<=n;x++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
			}
		}
	}

	//get profit[x][y]
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			for(int x=1;x<=k;x++) {
				if(a[i][x]==-1 || b[j][x]==-1) continue;
				profit[i][j] = max(profit[i][j], b[j][x] - a[i][x]);
			}
		}
	}

	//find answer
	long long l = 0, r = inf, mid, ans;
	while(l<=r) {
		mid = (l+r)/2;
		if(check(mid)) {
			ans = mid;
			l = mid+1;
		}
		else r = mid-1;
	}
	printf("%lld",ans);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:30:6: warning: unused variable 'i' [-Wunused-variable]
  int i,j,x,y;
      ^
merchant.cpp:30:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,x,y;
        ^
merchant.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld",&a[i][j],&b[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld",&x,&y,&val);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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