Submission #533358

#	Time	Username	Problem	Language	Result	Execution time	Memory
533358		new_acc	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	203 ms	3872 KiB

merchant

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=1e2+10;
const ll INF=1e18;
vector<pair<int,int> >graf[N];
pair<ll,int>pom[N][N];
ll curr[N][N];
bitset<N>vis;
pair<int,int>t[N][1001];
ll odl[N];
int n,m,k;
void Dijkstra(int xd){
	for(int i=1;i<=n;i++) vis[i]=0;
	set<pair<ll,int> >s;
	s.insert({0,xd});
	while(s.size()){
		auto it=s.begin();
		pair<ll,int> v=*it;
		s.erase(it);
		if(vis[v.se]) continue;
		vis[v.se]=1;
		odl[v.se]=v.fi;
		for(auto [u,c]:graf[v.se]){
			ll pom=c+v.fi;
			if(!vis[u]) s.insert({pom,u});
		}
	}
}
bool check(ll x){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(pom[i][j].fi==-1) curr[i][j]=-INF;
			else curr[i][j]=pom[i][j].se-pom[i][j].fi*x;
			curr[i][j]*=(-1LL);
		}
	}
	for(int sr=1;sr<=n;sr++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(curr[i][j]>curr[i][sr]+curr[sr][j] and curr[i][sr]!=INF and curr[sr][j]!=INF) 
					curr[i][j]=curr[i][sr]+curr[sr][j];
			}
		}
	}
	bool res=0;
	for(int i=1;i<=n;i++) if(curr[i][i]<=0) res=1;
	return res;
}
int bs(){
	int res=0,kon=1e9,pocz=1,sr;
	while(pocz<=kon){
		sr=(pocz+kon)>>1;
		if(check(sr)) res=sr,pocz=sr+1;
		else kon=sr-1;
	}
	return res;
}
void solve(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++) cin>>t[i][j].fi>>t[i][j].se;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		graf[a].push_back({b,c});
	}
	for(int v=1;v<=n;v++){
		Dijkstra(v);
		for(int i=1;i<=n;i++){
			if(!vis[i] or i==v) pom[v][i].fi=-1;
			else{
				pom[v][i].fi=odl[i];
				for(int j=1;j<=k;j++) if(t[v][j].fi!=-1 and t[i][j].se!=-1) pom[v][i].se=max(pom[v][i].se,t[i][j].se-t[v][j].fi);
			}
		}
	}
	cout<<bs()<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message (stderr)

merchant.cpp: In function 'void Dijkstra(int)':
merchant.cpp:26:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |   for(auto [u,c]:graf[v.se]){
      |            ^

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