Submission #1170701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170701		Muhammet	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	10 ms	1088 KiB

merchant

#include "bits/stdc++.h"

using namespace std;

const int N = 1e2 + 5;

vector <pair <int, int>> v[N];

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

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

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

	priority_queue <pair <int, int>> q;
	vector <vector <int>> dis(n+1, vector <int> (n+1, 1e9 + 5));
	for(int i = 1; i <= n; i++) {
		q.push({0, i});
		dis[i][i] = 0;
		while(!q.empty()) {
			auto [w, x] = q.top();
			q.pop();
			w *= (-1);
			if(dis[i][x] != w) continue;
			for(auto [j, w_] : v[x]) {
				if(dis[i][j] > w + w_) {
					dis[i][j] = w + w_;
					q.push({-dis[i][j], j});
				}
			}
		}
	}

	int ans = 0;
	for(int i = 2; i <= n; i++) {
		for(int j = 1; j <= k; j++) {
			if(b[1][j] == -1 or s[i][j] == -1) continue;
			ans = max(ans, (s[i][j] - b[1][j]) / (dis[1][i] + dis[i][1]));
		}
	}

	cout << ans << '\n';

	return 0;
}

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