Submission #1170823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170823		tkm_algorithms	여행하는 상인 (APIO17_merchant)	C++20	12 / 100	10 ms	1856 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;
const int inf = 1e9+1;

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];
	}
    
	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;
		g[u].push_back({v, w});
	}
	
	int dis[n+1][n+1];
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= n; ++j)dis[i][j] = inf;
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // dist, where are we.
	for (int i = 1; i <= n; ++i) {
		q.push({0, i});
		while (!q.empty()) {
			int u = q.top().second, w = q.top().first;
			q.pop();
			
			for (auto [j, c]: g[u]) {
				if (dis[i][j] > w+c) {
					q.push({w+c, j});
					dis[i][j] = w+c;
				}
			}
		}
	}
	
	int ans = 0;
	for (int i = 2; i <= n; ++i) {
		for (int j = 1; j <= k; ++j) {
			if (b[1][j] == -1 || s[i][j] == -1)continue;
			ans = max(ans, (s[i][j]-b[1][j])/(dis[1][i]+dis[i][1]));
		}
	}
	cout << ans;
	return 0;
}

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