Submission #981235

#	Time	Username	Problem	Language	Result	Execution time	Memory
981235		pcc	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	77 ms	3984 KiB

merchant

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

#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 110;
const ll inf = 1e18;

int N,M,K;

struct Edge{
	int f,t;
	ll c,w;
	Edge(int ff = 0,int tt = 0,ll cc = 0,ll ww = 0):f(ff),t(tt),c(cc),w(ww){};
};
vector<Edge> edges;

namespace S1{//get all pair shortest path+max profit
	ll dist[mxn][mxn];
	pii shop[mxn][mxn*10];
	void init(){
		for(auto &i:dist)for(auto &j:i)j = inf;
		for(int i = 1;i<=N;i++)dist[i][i] = 0;
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=K;j++)cin>>shop[i][j].fs>>shop[i][j].sc;
		}
		for(int i = 0;i<M;i++){
			int a,b,c;
			cin>>a>>b>>c;
			dist[a][b] = min(dist[a][b],1ll*c);
		}
	}
	void GO(){
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=N;j++){
				for(int k = 1;k<=N;k++){
					dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k]);
				}
			}
		}
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=N;j++){
				if(i == j||dist[i][j]>=inf)continue;
				int pr = 0;
				for(int k = 1;k<=K;k++){
					if(shop[i][k].fs == -1||shop[j][k].sc == -1)continue;
					pr = max(pr,shop[j][k].sc-shop[i][k].fs);
				}
				edges.push_back(Edge(i,j,pr,dist[i][j]));
			}
		}
		return;
	}
}

namespace S2{//binary search+BF
	ll dist[mxn];
	int relax[mxn];
	bool check(ll coef){
		memset(relax,0,sizeof(relax));
		memset(dist,0,sizeof(dist));
		bool flag = false;
		for(int i = 0;i<=N+10;i++){
			for(auto &e:edges){
				ll d = coef*e.w-e.c;
				//cerr<<e.f<<' '<<e.t<<':'<<d<<endl;
				if(dist[e.f]+d<=dist[e.t]){
					relax[e.t] = max(relax[e.t],relax[e.f]+1);
					dist[e.t] = dist[e.f]+d;
				}
				if(relax[e.f]>=N+1)flag = true;
			}
		}
		/*
		cerr<<coef<<":"<<endl;
		for(int i = 1;i<=N;i++)cerr<<dist[i]<<' ';cerr<<endl;
		for(int i = 1;i<=N;i++)cerr<<relax[i]<<' ';cerr<<endl;

	   */
		return flag;
	}
	void GO(){
		ll l = -1,r = 1e9;
		while(l != r){
			ll mid = l+(r-l+1)/2;
			if(check(mid))l = mid;
			else r = mid-1;
		}
		cout<<l<<'\n';
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>K;
	S1::init();
	S1::GO();
	//for(auto &i:edges)cerr<<i.f<<' '<<i.t<<' '<<i.w<<' '<<i.c<<endl;
	S2::GO();
}

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