Submission #248871

#	Time	Username	Problem	Language	Result	Execution time	Memory
248871		patrikpavic2	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	123 ms	4272 KiB

merchant

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll INF = (ll)1e9;

const int N = 105;
const int K = 1005;

ll dis[N][N], dp[N][N], zar[N][N], B[N][K], S[N][K];
int n, m, q;

void floyd(){
	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]);
}

bool mogu(ll x){
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			dp[i][j] = x * dis[i][j] - zar[i][j];
	for(int k = 1;k <= n;k++)
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	for(int i = 1;i <= n;i++)
		if(dp[i][i] <= 0)
			return 1;
	return 0;
}

int main(){
	scanf("%d%d%d", &n, &m, &q);	
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= q;j++)
			scanf("%lld%lld", &B[i][j], &S[i][j]);
		for(int j = 1;j <= n;j++)
			dis[i][j] = INF;
	}
	for(;m--;){
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		dis[x][y] = z;
	}
	floyd();
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			for(int k = 1;k <= q;k++)
				if(B[i][k] != -1 && S[j][k] != -1)
					zar[i][j] = max(zar[i][j], S[j][k] - B[i][k]);
	ll ans = 0;
	for(int i = 30;i >= 0;i--)
		if(mogu((1LL << i) + ans))
			ans += (1LL << i);
	printf("%lld\n", ans);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q); 
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:42:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &B[i][j], &S[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d%d%d", &x, &y, &z);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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