Submission #263668

#	Time	Username	Problem	Language	Result	Execution time	Memory
263668		define	Travelling Merchant (APIO17_merchant)	C++11	12 / 100	20 ms	3200 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int N,M,K;
int sell[105][1005],buy[105][1005];
vector<P>G[105];
int dis0[105],disv[105];
void dijkstra(int start,int *dis){
	fill(dis,dis+N,inf);
	dis[start]=0;
	priority_queue<P,vector<P>,greater<P>>que;
	que.push({0,start});
	while(!que.empty()){
		P p=que.top();que.pop();
		if(dis[p.second]<p.first)continue;
		for(P e:G[p.second]){
			if(dis[e.first]>p.first+e.second){
				dis[e.first]=p.first+e.second;
				que.push({dis[e.first],e.first});
			}
		}
	}
}
int solve(int vertex){
	dijkstra(vertex,disv);
	int distance=dis0[vertex]+disv[0];
	int diff=0;
	rep(i,K){
		if(sell[vertex][i]==-1||buy[0][i]==-1)continue;
		chmax(diff,sell[vertex][i]-buy[0][i]);
	}
	return diff/distance;
}
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>M>>K;
	rep(i,N)rep(j,K)cin>>buy[i][j]>>sell[i][j];
	rep(i,M){
		int a,b,c;cin>>a>>b>>c;a--;b--;
		G[a].push_back({b,c});
	}
	int ans=0;
	dijkstra(0,dis0);
	REP(i,N)chmax(ans,solve(i));
	cout<<ans<<endl;
}

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