Submission #937016

#	Time	Username	Problem	Language	Result	Execution time	Memory
937016		ByeWorld	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	41 ms	1876 KiB

merchant

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int long long
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<string, pii> ipii;
const int INF = 1e18+10;
const int MAXN = 110;
const int MAXK = 1010;
const int LOG = 20;

int n, m, k;
int b[MAXN][MAXK], s[MAXN][MAXK];
vector <pii> adj[MAXN][3];
int dis[MAXN][3];
priority_queue <pii> pq;

void dji(int nw, int ty){
	for(int i=1; i<=n; i++) dis[i][ty] = INF;
	pq.push({0, nw});
	dis[nw][ty] = 0;

	while(!pq.empty()){
		int nw = pq.top().se; int dist = pq.top().fi; pq.pop();
		if(dist > dis[nw][ty]) continue;

		for(auto ed : adj[nw][ty]){
			int wei = ed.se, nx = ed.fi;
			if(dis[nx][ty] <= dis[nw][ty] + wei) continue;
			dis[nx][ty] = dis[nw][ty] + wei;
			pq.push({dis[nx][ty], nx});
		}
	}
}
signed main(){
	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++){
		int x, y, z; cin >> x >> y >> z;
		adj[x][0].pb({y, z});
		adj[y][1].pb({x, z});
	}
	dji(1, 0);
	dji(1, 1);
	int ans = 0;
	//cout << norm << " p\n";

	for(int i=2; i<=n; i++){
		int val = 0;
		for(int j=1; j<=k; j++){
			if(s[i][j] == -1 || b[1][j] == -1) continue;
			int te = s[i][j] - b[1][j];
			val = max(val, te);
		}
		int dist = dis[i][0] + dis[i][1];
		ans = max(ans, val / dist );
		//cout << i << ' ' << dist << ' ' << val << " dist\n";
	}
	cout << ans << '\n';
}

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