제출 #1171282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171282		Muhammet	여행하는 상인 (APIO17_merchant)	C++17	100 / 100	55 ms	2120 KiB

merchant

#include "bits/stdc++.h"

using namespace std;

#define ll long long

const int N = 1e2 + 5;

ll n, m, k, ans = 1e12 + 1;

vector <vector <ll>> dis, e, b, s, e1;

bool check(ll x1) {
	e1 = e;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			e1[i][j] -= (x1 * dis[i][j]);
			e1[i][j] *= (-1);
		}
	}
	for(int x = 1; x <= n; x++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				e1[i][j] = min(e1[i][j], e1[i][x] + e1[x][j]);
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		if(e1[i][i] <= 0) return true;
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m >> k;
	b.assign(n+1, vector <ll> (k+1, 0)), s.assign(n+1, vector <ll> (k+1, 0));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= k; j++) {
			cin >> b[i][j] >> s[i][j];
		}
	}

	dis.assign(n+1, vector <ll> (n+1, 1e9)); 

	for(int i = 1; i <= m; i++) {
		int u1, u2, w;
		cin >> u1 >> u2 >> w;
		dis[u1][u2] = w;
	}

	for(int x = 1; x <= n; x++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				dis[i][j] = min(dis[i][j], dis[i][x] + dis[x][j]);
			}
		}
	}

	e.assign(n+1, vector <ll> (n+1, 0));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			for(int x = 1; x <= k; x++) {
				if(b[i][x] == -1 or s[j][x] == -1) continue;
				e[i][j] = max(e[i][j], (s[j][x] - b[i][x]));
			}
		}
	}

	ll l = 0, r = 1e9;
	while(l <= r) {
		ll md = (l + r) / 2;
		if(check(md)) {
			l = md+1;
			ans = md;
		}
		else {
			r = md-1;
		}
	}

	cout << (ans == 1e12 + 1 ? -1 : ans);

	return 0;
}

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