Submission #673046

#	Time	Username	Problem	Language	Result	Execution time	Memory
673046		Dan4Life	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	68 ms	1916 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define fi first
#define se second
using ll = long long;
const int maxn = (int)1e2+10;
const int maxk = (int)1e3+10;
const ll LINF = (ll)1e18;

int n, m, k;
int a[maxn][maxk][2];
int dis[maxn][maxn];
vector<pair<int,int>> adj[maxn];


int32_t main()
{
	int n, m, k, ans = 0, path=LINF;
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < k; j++)
			cin >> a[i][j][0] >> a[i][j][1];
	for(int i = 0; i < n; i++)
		fill(dis[i],dis[i]+maxn,LINF);
	for(int i = 0; i < m; i++){
		int a, b, c; cin >> a >> b >> c; a--, b--;
		adj[a].pb({b,c}); dis[a][b]=min(dis[a][b],c);
	}
	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
	for(int j = 0; j < k; j++) 
		if(a[0][j][0]!=-1 and a[0][j][1]!=-1) 
			ans+=max(0ll, a[0][j][1]-a[0][j][0]);
	for(int i = 1; i < n; i++){
		bool ok = 0; int cost=0;
		for(auto u : adj[i]) if(u.fi==0) ok=1,cost=u.se;
		if(ok) path = min(path, dis[0][i]+cost);
	}
	cout << ans/path;
}

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