Submission #703774

#	Time	Username	Problem	Language	Result	Execution time	Memory
703774		Dan4Life	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	55 ms	3148 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];
int vis[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], ans+=max(a[i][j][1]-a[i][j][0], 0ll);
	for(int i = 0; i < n; i++)
		fill(dis[i],dis[i]+maxn,LINF), dis[i][i]=0;
	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 i = 2; i <= n; i++) path = min(path, dis[1][i]+dis[i][1]);
	cout << ans/path;
}

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