Submission #422767

#	Time	Username	Problem	Language	Result	Execution time	Memory
422767		QCFium	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	633 ms	4484 KiB

merchant

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

template<typename T> using pqueue_inv = std::priority_queue<T, std::vector<T>, std::greater<T> >;


int main() {
	int n = ri();
	int m = ri();
	int k = ri();
	int val[n][k][2];
	for (auto &i : val) for (auto &j : i) for (auto &k : j) k = ri();
	
	struct Hen {
		int a;
		int b;
		int64_t c;
	};
	std::vector<Hen> hens(m);
	for (auto &i : hens) i.a = ri() - 1, i.b = ri() - 1, i.c = ri();
	
	std::vector<std::vector<int64_t> > dist_base;
	for (int i = 0; i < n; i++) {
		std::vector<std::pair<int, int> > hen[n];
		for (auto i : hens) hen[i.a].push_back({i.b, i.c});
		std::vector<int64_t> dist(n, 1000000000000000000);
		pqueue_inv<std::pair<int64_t, int> > que;
		que.push({dist[i] = 0, i});
		while (que.size()) {
			auto j = que.top();
			que.pop();
			if (j.first != dist[j.second]) continue;
			for (auto k : hen[j.second]) if (dist[k.first] > j.first + k.second)
				que.push({dist[k.first] = j.first + k.second, k.first});
		}
		dist_base.push_back(dist);
	}
	
	int l = 0;
	int r = 1000000001;
	while (r - l > 1) {
		int mid = l + ((r - l) >> 1);
		
		std::vector<Hen> hens_cur;
		for (auto i : hens) hens_cur.push_back({i.a, i.b, i.c * mid});
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int max = -1;
				for (int l = 0; l < k; l++) if (val[i][l][0] != -1 && val[j][l][1] != -1) max = std::max(max, val[j][l][1] - val[i][l][0]);
				if (max > 0) hens_cur.push_back({i, j, (int64_t) dist_base[i][j] * mid - max});
			}
		}
		
		std::vector<std::pair<int64_t, int> > dist(n, {1000000000000000000, 1000000000});
		bool loop = false;
		for (int i = 0; i <= n; i++) {
			for (auto j : hens_cur) {
				std::pair<int64_t, int> cur_dist;
				if (i) cur_dist = dist[j.a];
				else cur_dist = {0, 1000000000};
				if (cur_dist.first == 1000000000000000000) continue;
				cur_dist.first += j.c;
				cur_dist.second--;
				if (dist[j.b] > cur_dist) {
					dist[j.b] = cur_dist;
					if (i == n) loop = true;
				}
			}
		}
		if (loop) l = mid;
		else r = mid;
	}
	printf("%d\n", l);
	
	
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int ri()':
merchant.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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