Submission #1312783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312783		salmon	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	71 ms	2400 KiB

merchant

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

int N;
int M;
int K;
long long int inf = 1.1e18;
long long int adjmat[110][110];
long long int sellmat[110][110];
long long int tempmat[110][110];

long long int b[110][1100];
long long int s[110][1100];

int main(){
	
	scanf(" %d",&N);
	scanf(" %d",&M);
	scanf(" %d",&K);
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= K; j++){
			scanf(" %lld",&b[i][j]);
			scanf(" %lld",&s[i][j]);
		}
	}
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			adjmat[i][j] = 1'000'000'000;
			sellmat[i][j] = 0;
		}
	}
	
	for(int i = 0; i < M; i++){
		int u,v,t;
		
		scanf(" %d",&u);
		scanf(" %d",&v);
		scanf(" %d",&t);
		
		
		adjmat[u][v] = min(adjmat[u][v],(long long)t);
	}
	
	for(int k = 1; k <= N; k++){
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				if(i == k) continue;
				if(k == j) continue;
				adjmat[i][j] = min(adjmat[i][k] + adjmat[k][j],adjmat[i][j]);
			}
		}
	}

	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			sellmat[i][j] = 0;
		}
	}
	
	for(int k = 1; k <= K; k++){
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				if(s[j][k] != -1 && b[i][k] != -1) sellmat[i][j] = max(sellmat[i][j], s[j][k] - b[i][k]);
			}
		}
	}
	
	long long int s = 0;
	long long int e = 1'000'000'000;

	while(s != e){
		long long int m = (s + e + 1)/2;
		
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				if(i == j) tempmat[i][j] = inf;
				
				tempmat[i][j] = adjmat[i][j] * m - sellmat[i][j]; 
			}
		}
		
		bool can = false;
		
		for(int k = 1; k <= N; k++){
			for(int i = 1; i <= N; i++){
				for(int j = 1; j <= N; j++){
					tempmat[i][j] = min(tempmat[i][k] + tempmat[k][j],tempmat[i][j]);
					if(tempmat[i][j] < -inf){
						can = true;
					}
				}
			}
		}
		
		
		
		for(int i = 1; i <= N; i++){
			can |= (tempmat[i][i] <= 0);
		}
	
		if(can){
			s = m;
		}
		else{
			e = m - 1;
		}
	}
	
	printf("%lld",s);
	
}
/*
4 5 2
1 -1 -1 -1
-1 1000 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
 */

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
merchant.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
merchant.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf(" %d",&K);
      |         ~~~~~^~~~~~~~~~
merchant.cpp:23:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                         scanf(" %lld",&b[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~
merchant.cpp:24:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |                         scanf(" %lld",&s[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~
merchant.cpp:38:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
merchant.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~
merchant.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |                 scanf(" %d",&t);
      |                 ~~~~~^~~~~~~~~~

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