oj.uz

답안 #945345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945345 2024-03-13T16:31:41 Z TAhmed33 여행하는 상인 (APIO17_merchant) C++
0 / 100
 103 ms 4700 KB 
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const ll inf = LLONG_MAX / 2;
const int MAXN = 100 + 25;
ll s[MAXN][1001], b[MAXN][1001]; int n, m, k;
ll adj[MAXN][MAXN], adj2[MAXN][MAXN], val[MAXN][MAXN];
bool check (ll x) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			adj2[i][j] = x * min(inf / x, adj[i][j]) - val[i][j];
		}
	}
	bool flag = 0;
	for (int l = 1; l <= n; l++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				adj2[i][j] = min(adj2[i][j], adj2[i][l] + adj2[l][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) flag |= adj2[i][i] <= 0;
	return flag;
}
int main () {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			int x, y; cin >> x >> y;
			b[i][j] = x, s[i][j] = y;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			adj[i][j] = inf;	
		}
	}
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		adj[a][b] = c;
	}
	for (int l = 1; l <= n; l++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				adj[i][j] = min(adj[i][j], adj[i][l] + adj[l][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int l = 1; l <= k; l++) {
				if (b[i][l] != -1 && s[j][l] != -1) {
					val[i][j] = max(val[i][j], s[j][l] - b[i][l]);
				}
			}
		}
	}
	ll l = 1, r = 1e9, ans = -1;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (check(mid)) {
			r = mid - 1; 
		} else {
			l = mid + 1;
		}
	}
	cout << (long long)(r) << '\n';
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:58:21: warning: unused variable 'ans' [-Wunused-variable]
   58 |  ll l = 1, r = 1e9, ans = -1;
      |                     ^~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 103 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -