Submission #57279

#	Time	Username	Problem	Language	Result	Execution time	Memory
57279		IvanC	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	155 ms	10244 KiB

merchant

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

typedef long long ll;

const int MAXN = 110;
const int MAXM = 1010;
const ll INF = 1e17;

ll compra[MAXN][MAXM],venda[MAXN][MAXM];
ll matriz[MAXN][MAXN],lucro[MAXN][MAXN];
int chega[MAXN][MAXN],existe[MAXN][MAXN];
ll shortest_path[MAXN][MAXN];
int N,M,K;

int FloydWarshall(ll X){
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			shortest_path[i][j] = INF;
			existe[i][j] = 0;
		}
	}
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			if(!chega[i][j]) continue;
			shortest_path[i][j] = X*matriz[i][j] - lucro[i][j];
			existe[i][j] = 1;
		}	
	}
	
	for(int k = 1;k<=N;k++){
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=N;j++){
				if(!existe[i][k] || !existe[k][j]) continue;
				existe[i][j] |= 1;
				shortest_path[i][j] = min(shortest_path[i][j], shortest_path[i][k] + shortest_path[k][j] );
			}
		}
	}
	
	for(int i = 1;i<=N;i++){
		if(shortest_path[i][i] <= 0) return 1;
	}
	
	return 0;
	
}

ll bruta_par(int u,int v){
	ll best = 0;
	for(int i = 1;i<=K;i++){
		if(compra[u][i] != -1 && venda[v][i] != -1) best = max(best, venda[v][i] - compra[u][i] );
	}
	return best;
}

void calcula_lucro(int v){
	for(int i = 1;i<=N;i++){
		lucro[v][i] = bruta_par(v,i);
	}
}

int main(){
	
	scanf("%d %d %d",&N,&M,&K);
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			matriz[i][j]  = INF;
		}
	}
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=K;j++){
			scanf("%lld %lld",&compra[i][j],&venda[i][j]);
		}
	}
	//printf("Custos\n");
	for(int i = 1;i<=N;i++) calcula_lucro(i);
	for(int i = 1;i<=M;i++){
		int u,v;
		ll w;
		scanf("%d %d %lld",&u,&v,&w);
		matriz[u][v] = w;
		chega[u][v] = 1;
	}
	//printf("Leu\n");
	
	for(int k = 1;k<=N;k++){
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=N;j++){
				if(!chega[i][k] || !chega[k][j]) continue;
				chega[i][j] |= 1;
				matriz[i][j] = min(matriz[i][j],matriz[i][k] + matriz[k][j]);
			}
		}
	}
	
	//printf("Floyd\n");
	//for(int i = 1;i<=N;i++){
	//	printf("%d :",i);
	//	for(int j = 1;j<=N;j++){
	//		printf(" (%lld,%lld)", chega[i][j] ? (matriz[i][j]) : (-1), lucro[i][j] );
	//	}
	//	printf("\n");
	//}
	
	ll resposta = 0,ini = 1,fim = lucro[1][1],meio;
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			fim = max(fim,lucro[i][j]);
		}
	}
	while(ini <= fim){
		meio = ini + (fim - ini)/2;
		if(FloydWarshall(meio)){
			resposta = meio;
			ini = meio + 1;
		}
		else{
			fim = meio - 1;
		}
	}
	printf("%lld\n",resposta);
	
	return 0;	
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:65: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:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld %lld",&compra[i][j],&venda[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&u,&v,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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