Submission #1040631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040631		Muhammet	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	9 ms	12636 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second

const ll N = 3005;
const ll M = 1e9 + 7;

ll T, n, m, k, b[N][N], s[N][N], dis[N][N];

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

int main(){
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m >> k;
	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++){
		ll u1, u2, u3;
		cin >> u1 >> u2 >> u3;
		v[u1].push_back({u2,u3});
	}

	ll ans = 0;
	for(int i = 1; i <= k; i++){
		if(b[1][i] != -1) ans += max(0LL,s[1][i]-b[1][i]);
	}

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

	ll mn = 1e9;
	for(int i = 2; i <= n; i++){
		ll a1 = dis[i][1];
		a1 += dis[1][i];
		mn = min(mn, a1);
	}

	if(mn == 1e9 or mn == 0){
		cout << 0;
	}
	else {
		ans /= mn;
		cout << ans;
	}

	return 0;
}

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