oj.uz

답안 #230025

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230025 2020-05-07T20:19:41 Z MetB 여행하는 상인 (APIO17_merchant) C++14
0 / 100
 134 ms 720 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
#define N 1000003
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = 1e17, MOD = INF + 7, MOD2 = 1e6 + 3;

ll un_dist[100][100], deal[100][100];
ll sell[100][100], buy[100][100], n, m, k;
ll d[100][100];

bool check (int x) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (un_dist[i][j] == INF) d[i][j] = -INF;
			else d[i][j] = deal[i][j] - x * un_dist[i][j];
		}


	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (d[i][j] < d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j];

	for (int i = 0; i < n; i++)
		if (d[i][i] >= 0) return true;

	return false;
}
 
int main () {
	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < k; j++) {
			int b, s;
			cin >> buy[i][j] >> sell[i][j];
		}

	for (int i = 0; i < n; i++)
		fill (un_dist[i], un_dist[i] + n, (int) INF);

	for (int i = 0; i < m; i++) {
		int u, v, l;
		cin >> u >> v >> l;
		u--, v--;
		un_dist[u][v] = l;
	}

	for (int k = 0; k < n; k++) 
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				un_dist[i][j] = min (un_dist[i][j], un_dist[i][k] + un_dist[k][j]);


	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int it = 0; it < k; it++)
				if (sell[j][it] > 0 && buy[i][it] > 0)
					deal[i][j] = max (d[i][j], sell[j][it] - buy[i][it]);

	int l = 0, r = 1e9;

	while (l < r) {
		int mid = (l + r + 1) / 2;
		if (check (mid)) l = mid;
		else r = mid - 1;
	}

	cout << l << endl;
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:43:8: warning: unused variable 'b' [-Wunused-variable]
    int b, s;
        ^
merchant.cpp:43:11: warning: unused variable 's' [-Wunused-variable]
    int b, s;
           ^

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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