Submission #732258

#	Time	Username	Problem	Language	Result	Execution time	Memory
732258		1ne	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	20 ms	4436 KiB

merchant

/*
*  author : Apiram                  
*  created: 29.04.2023 02:41:46
*/

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m,k;cin>>n>>m>>k;
	vector<vector<int>>b(n),s(n);
	for (int i = 0;i<n;++i){
		for (int j =0;j<k;++j){
			int x,y;cin>>x>>y;
			b[i].push_back(x);
			s[i].push_back(y);
		}
	}
	vector<vector<pair<int,long long>>>adj(n);
	for (int i = 0;i<m;++i){
		int x,y,cost;
		cin>>x>>y>>cost;
		--x;--y;
		adj[x].push_back({y,cost});	
	}
	long long ans = 0;	
	for (int j = 0;j<n;++j){	
		vector<vector<vector<long long>>>min_t(n,vector<vector<long long>>(n,vector<long long>(2,1e16)));
		for (int i = 0;i<n;++i){
			queue<int>q;
			q.push(i);
			min_t[i][i][0] = 0;
			if (i == j){
				min_t[i][i][1] = 0;
				min_t[i][i][0] = 1e16;
			}
			vector<bool>hv(n,false);
			hv[i] = true;
			while(!q.empty()){
				auto u = q.front();
				q.pop();
				hv[u] = false;
				for (auto x:adj[u]){
					bool need = false;
					if (x.first != j && u != j && min_t[i][x.first][0] > min_t[i][u][0] + x.second){
						min_t[i][x.first][0] = min_t[i][u][0] + x.second;
						need = true;
					}
					if (x.first == j && min_t[i][x.first][1] > min_t[i][u][0] + x.second){
						min_t[i][x.first][1] = min_t[i][u][0] + x.second;
						need = true;
					}
					if (min_t[i][x.first][1] > min_t[i][u][1] + x.second){
						min_t[i][x.first][1] = min_t[i][u][1] + x.second;
						need = true;
					}
					if (need && !hv[x.first]){
						q.push(x.first);
						hv[x.first] = true;
					}
				}
			}	
		}
		for (int i = 0;i<n;++i){
			for (int p = 0;p<k;++p){
				if (min_t[j][i][1]==1e16 || min_t[i][j][1]==1e16)continue;
				if (b[j][p]==-1)continue;
				if (s[i][p] == -1)continue;
				long long tt = min_t[j][i][1] + min_t[i][j][1];
				ans = max(ans,(s[i][p] - b[j][p]) / tt); 
			}		
		}
	}
	cout<<ans<<'\n';		
	return 0;
}

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