Submission #1021074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021074		JuliaTatad	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	99 ms	3684 KiB

merchant

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n, m, k; 
long long int INF = 2 * 1e18;
vector<vector<pair<int, int>>> markets; vector<vector<int>> gr; vector<vector<int>> profits;
vector<bool> used;

long long int MIN(long long int a, long long int b) {
	if (a < b) {
		return a;
	}
	return b;
}

struct Edge {
	int from, to, w;
	Edge(int from, int to, int w) : from(from), to(to), w(w) {}
};

void dfs(int v) {
	used[v] = true;
	for (auto u : gr[v]) {
		if (!used[u]) {
			dfs(u);
		}
	}
}

int main() {
	cin >> n >> m >> k; markets.resize(n, vector<pair<int, int>>(k));
	vector<vector<long long int>> d(n, vector<long long int>(n, INF));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			cin >> markets[i][j].first; cin >> markets[i][j].second;
		}
	}
	gr.resize(n); vector<Edge> edges;
	for (int i = 0; i < m; i++) {
		int v, u, t; cin >> v >> u >> t; v--; u--;
		gr[v].push_back(u); edges.push_back(Edge(v, u, t)); 
	}
	profits.assign(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int x = 0; x < k; x++) {
				if (markets[i][x].first != -1 && markets[j][x].second != -1) {
					profits[i][j] = max(profits[i][j], -markets[i][x].first + markets[j][x].second);
				}
			}
		}
	}

	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << "profits[" << i << "][" << j << "] = " << profits[i][j] << endl;
		}
	}
	*/
	
	vector<vector<double>> len(n, vector<double>(n, INF));
	/*
	for (int i = 0; i < n; i++) {
		len[i][i] = 0;
	}
	*/
	for (auto& e : edges) {
		len[e.from][e.to] = MIN(len[e.from][e.to], e.w);
	}
	for (int x = 0; x < n; x++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (len[i][x] < INF && len[x][j] < INF) {
					len[i][j] = MIN(len[i][j], len[i][x] + len[x][j]);
				}
			}
		}
	}
	
	/*
	d.assign(n, vector<long long int>(n, INF));
	long long int m = 0;

	for (int i = 0; i < n; i++) {
		d[i][i] = 0;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (len[i][j] < INF) {
				d[i][j] = m * len[i][j] - profits[i][j];
			}
		}
	}

	for (int x = 0; x < n; x++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (d[i][x] < INF && d[x][j] < INF) {
					d[i][j] = MIN(d[i][j], d[i][x] + d[x][j]);
				}
			}
		}
	}
	int cycles = 0;
	for (int i = 0; i < n; i++) {
		if (d[i][i] < 0) {
			cycles = 1;
		}
	}
	if (cycles == 0) {
		cout << 0 << "\n"; return 0;
	}

	*/

	long long int l = 0; long long int h = 2 * 1e9;
	while (l + 1 < h) {
		long long int m = (l + h) / 2;
		//double m = mid - 0.0001;
		d.clear(); d.assign(n, vector<long long int>(n, INF));
		/*
		for (int i = 0; i < n; i++) {
			d[i][i] = 0;
		}
		*/
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (len[i][j] < INF) {
					d[i][j] = m * len[i][j] - profits[i][j];
				}
			}
		}

		for (int x = 0; x < n; x++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (d[i][x] < INF && d[x][j] < INF) {
						d[i][j] = MIN(d[i][j], d[i][x] + d[x][j]);
					}
				}
			}
		}
		int cycles = 0;
		for (int i = 0; i < n; i++) {
			if (d[i][i] <= 0) {
				cycles = 1;
			}
		}
		if (cycles == 1) {
			l = m;
		}
		else {
			h = m;
		}
	}
	cout << l << "\n"; 
}

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