제출 #474005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474005		Hamed5001	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	116 ms	708 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mxN = 101;
ll N, M, K;
pair<ll, ll> MARKET[mxN][mxN];
bool vis[mxN+50][mxN+50];
vector<pair<ll, pair<ll, ll>>> adj[mxN];

ll ans = 0;

void dfs(ll node, ll st, ll t, ll profit, ll holding) {
	if (node == st && t) {
		if (!holding) {
			ans = max(ans, (ll)floor(profit/t));
		}
		return;
	}
	if (holding && ~MARKET[node][holding].second) {
		vis[node][0] = 1;
		dfs(node, st, t, profit + MARKET[node][holding].second, 0);
	}
	for (auto c : adj[node]) {
		if (!vis[c.first][holding]) {
			vis[c.first][holding] = 1;
			dfs(c.second.first, st, t + c.second.second, profit, holding);
		}
		if (!holding) {
			for (int i = 1; i <= K; i++) {
				if (~MARKET[node][i].first && !vis[c.first][i]) {
					vis[c.first][i] = 1;
					dfs(c.second.first, st, t + c.second.second, profit - MARKET[node][i].first, i);
				}
			}
		}
	}
}

void solve() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> MARKET[i][j].first >> MARKET[i][j].second;
		}
	}

	for (int i = 0; i < M; i++) {
		int U, V, T;
		cin >> U >> V >> T;
		adj[U].push_back({i, {V, T}});
	}

	for (int i = 1; i <= N; i++) {
		memset(vis, 0, sizeof vis);
		dfs(i, i, 0, 0, 0);
	}

	cout << ans ;
}	

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

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