Submission #107753

#	Time	Username	Problem	Language	Result	Execution time	Memory
107753		Just_Solve_The_Problem	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	131 ms	3452 KiB

merchant

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)1e2 + 7;
const ll inf = (ll)1e18;

int n, m, k;
vector<vector<int>> S, B;
ll dist[N][N], opt[N][N], dp[N][N];

bool check(int x) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dist[i][j] == inf) {
				dp[i][j] = inf;
			} else {
				dp[i][j] = dist[i][j] * x - opt[i][j];
			}
		}
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (dp[i][i] <= 0) return 1;
	}
	return 0;
}

main() {
	scanf("%d %d %d", &n, &m, &k);
	S.resize(n, vector<int>(k, 0));
	B.resize(n, vector<int>(k, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = inf;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			scanf("%d %d", &B[i][j], &S[i][j]);
		}
	}
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		u--;
		v--;
		dist[u][v] = w;
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int l = 0; l < k; l++) {
				if (B[i][l] >= 0 && S[j][l] >= 0)
					opt[i][j] = max(opt[i][j], -B[i][l] * 1LL + S[j][l]);
			}
		}
	}
	int l = 0;
	int r = 1e9 + 123;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	cout << l;
}

Compilation message (stderr)

merchant.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
merchant.cpp: In function 'int main()':
merchant.cpp:38: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:48:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &B[i][j], &S[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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