제출 #1040572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1040572		Muhammet	여행하는 상인 (APIO17_merchant)	C++17	0 / 100	14 ms	17244 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 = 305;
const ll M = 1e9 + 7;

ll T, n, m, k, b[N][N*10], s[N][N*10], 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++){
		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++){
		mn = min(mn, dis[i][1] + dis[1][i]);
	}
	if(mn == 1e9 or mn == 0) cout << 0;
	else cout << (ans/mn);

	return 0;
}

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