제출 #1014926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014926		idiotcomputer	여행하는 상인 (APIO17_merchant)	C++11	0 / 100	51 ms	2232 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define sz size 
#define pii pair<ll,ll>
#define f first
#define s second

const int mxN = 100;
const int mxK = 1e3;
const ll inf = 1e18;
int n,m,k;

ll d[mxN][mxN];
ll p[mxN][mxN];
pii vals[mxN][mxK];


bool solve(ll x){
	ll d2[n][n];
	for (int i =0; i < n; i++)	for (int j =0; j < n; j++){
		if (d[i][j] == inf || d[i][j] >= inf/x) d2[i][j] = inf;
		else d2[i][j] = d[i][j]*x-p[i][j];
	}
	for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
		if (d2[i][k] != inf && d2[k][j] != inf) d2[i][j] = min(d2[i][j],d2[i][k]+d2[k][j]);
	}

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
		if (i == j || d2[i][j] == inf || d2[j][i] == inf) continue;
		if (d2[i][j] + d2[j][i] <= 0) return true;
	}
	return false;
}

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

	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> vals[i][j].f >> vals[i][j].s;

	for (int i =0; i < n; i++){
		for (int j =0; j < n; j++) d[i][j] = inf;
		d[i][i] = 0;
	}

	ll v,w,t;
	for (int i = 0; i < m; i++){
		cin >> v >> w >> t;
		v -= 1;
		w -= 1;
		d[v][w] = min(d[v][w],(ll)t);
	} 

	for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
		if (d[i][k] != inf && d[k][j] != inf) d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
	}
/*	for (int i =0; i < n; i++){
		for (int j =0; j < n; j++) cout << d[i][j] << " ";
		cout << '\n';
	}*/
	memset(p,0,sizeof(p));
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int t = 0; t < k; t++){
		if (vals[i][t].f == -1 || vals[j][t].s == -1) continue;
		p[i][j] = max(p[i][j],vals[j][t].s - vals[i][t].f);
	}

/*	for (int i =0; i < n; i++){
		for (int j = 0; j < n; j++) cout << p[i][j] << " ";
		cout << '\n';
	}
*/
	ll l = 0;
	ll r = 1e9+1;
	ll c;
	while (r-l>1){
		c = (l+r)/2;
		if (solve(c)) l = c;
		else r = c;
	}
	cout << l << "\n";
	return 0;
}

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