제출 #407130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407130		inluminas	여행하는 상인 (APIO17_merchant)	C++14	100 / 100	118 ms	4164 KiB

merchant

#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
 
const int lmt=1e3+10,lmt2=1e2+10;
const ll inf=2e9;
ll n,m,k;
ll b[lmt2][lmt],s[lmt2][lmt],dis[lmt2][lmt2],ok[lmt2][lmt2],lob[lmt2][lmt2];
 
int main(){
	fastio;
 
	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<=n;i++){
		for(int j=1;j<=n;j++) dis[i][j]=inf;
	}
	for(int i=1;i<=m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		dis[u][v]=w;
	}
	for(int l=1;l<=n;l++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dis[i][j]>dis[i][l]+dis[l][j]){
					dis[i][j]=dis[i][l]+dis[l][j];
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dis[i][j]>=inf){
				lob[i][j]=-inf;
				continue;
			}
			for(int item=1;item<=k;item++){
				if(s[j][item]==-1 || b[i][item]==-1) continue;
				lob[i][j]=max(lob[i][j],s[j][item]-b[i][item]);
			}
		}
	}
	ll lo=0,hi=inf;
	while(lo<hi){
		ll mid=(lo+hi+1)/2;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dis[i][j]>=inf) ok[i][j]=-inf;
				else ok[i][j]=lob[i][j]-mid*dis[i][j];
			}
		}
		for(int l=1;l<=n;l++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(dis[i][l]>=inf || dis[j][l]>=inf) continue;
					ok[i][j]=max(ok[i][j],ok[i][l]+ok[l][j]);
				}
			}
		}
		bool on=0;
		for(int i=1;i<=n;i++){
			if(ok[i][i]>=0){
				on=1;
				break;
			}
		}
		if(on) lo=mid;
		else hi=mid-1;
	}
	cout<<lo<<endl;
}

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