Submission #1170812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170812		tkm_algorithms	여행하는 상인 (APIO17_merchant)	C++20	0 / 100	901 ms	1114112 KiB

merchant

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
	
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
 
const char nl = '\n';
const int N = 10005;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<vector<int>> b(n+1, vector<int> (k+1)), s(n+1, vector<int> (k+1));
    for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= k; ++j)
			cin >> b[i][j] >> s[i][j];
	}
    
    queue<tuple<int, int, int, int>> q; // where we, item, profit, path lenght.
	for (int i = 1; i <= k; ++i)
		q.push({1, i, -b[1][i], 0});
	
	map<pair<int, int>, int> mp;
	vector<tuple<int, int>> g[n+1]; // to where, lenght
	for (int i = 0; i < m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		int y = mp[{u, v}];
		if (y == 0 || y > w) {
			mp[{u, v}] = w;
		}
	}
	
	for (auto i: mp) {
		//cout << i.first
		g[i.first.first].push_back({i.first.second, i.second});
	}
	
	int ans = 0;
	while (!q.empty()) {
		auto [u, it, pr, len] = q.front();
		q.pop();
		
		if (u == 1 && len > 0) {
			ans = max(ans, pr/len);
			continue;
		}
		
		int onkiIt = it, onkiPr = pr;
		if (u != 1 && it > 0 && s[u][it] > -1) { // need to sell the item.
			pr += s[u][it];
			it = -1;
		}
		
		for (auto [i, w]: g[u]) {
			if (u != 1 && pr != onkiPr)q.push({i, -1, pr, len+w});
			q.push({i, onkiIt, onkiPr, len+w});
		}
	}
	
	cout << ans;
	return 0;
}

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