Submission #404978

#	Time	Username	Problem	Language	Result	Execution time	Memory
404978		CursedCode	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	28 ms	3216 KiB

merchant

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
 
const int MAXN = 100 + 3, INF = 1000 * 1000 * 1000 + 123, MAXK = 1000 + 23;
 
 
 
 
 
/*
4 5 2
10 9 5 2
-1 4 -1 15
-1 7 -1 9
-1 -1 -1 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/
 
 
 
 
 
 
 
 
 
 
int n, m, kk, d[MAXN][MAXN], b[MAXN][MAXK], s[MAXN][MAXK];
long double ans;
 
 
 
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m >> kk;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (i != j) d[i][j] = INF;
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < kk; j++){
			cin >> b[i][j] >> s[i][j];
		}
	}
	for (int i = 1; i < n; i++){
		for(int j = 0; j < kk; j++){
			if (b[i][j] != -1) return 0;
		}
	}
	int v, w, t;
	for (int i = 0; i < m; i++) {
		cin >> v >> w >> t;
		d[v--][w--] = t;
	}
	for (int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	for (int i = 1; i < n; i++) {
		for(int j = 0; j < kk; j++){
			if(~b[0][j] && ~s[i][j]) ans = max(ans, (long double)(s[i][j] - b[0][j]) / (d[0][i] + d[i][0]));
		}
	}
	cout << (int)ans;
	return 0;
}

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