제출 #64250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64250		khohko	여행하는 상인 (APIO17_merchant)	C++17	21 / 100	1089 ms	2440 KiB

merchant

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define ARRS ((ll)(2e6+500))
#define MAX ((ll)(1e18+100))
#define MOD ((ll)1e6+7)
#define mi(a,b) a=min((a),(b))


ll n,m,k;
pair<ll,ll> q[200][200];
__int128 f[200][200];
__int128 v[200][200];


int main(){
	#ifdef KHOKHO
			freopen("in.in","r",stdin);
			freopen("out.out","w",stdout);
	#endif
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	//cout<<n<<" "<<k<<endl;
	for(int i=0; i<n; i++)
		for(int j=0; j<k; j++)
			cin>>q[i][j].fr>>q[i][j].sc;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			f[i][j]=f[j][i]=MAX;
	for(int i=0; i<m; i++){
		ll k,p,c;
		cin>>k>>p>>c;
		k--;
		p--;
		f[k][p]=c;
	}
	//return 0;
	for(int k=0; k<n; k++)
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

	__int128 l=0,r=MAX;
	while(l<r){
		__int128 em=(l+r+1)>>1ll;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				v[i][j]=-em*f[i][j];
				for(int t=0; t<k; t++){
					if(q[i][t].fr>=0&&q[j][t].sc>=0)
						v[i][j]=max(v[i][j],(__int128)q[j][t].sc-q[i][t].fr-em*f[i][j]);
				}
			}
		}
		for(int k=0; k<n; k++){
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					v[i][j]=max(v[i][j],v[i][k]+v[k][j]);
				}
			}
		}
		bool e=0;
		for(int i=0; i<n; i++){
			if(v[i][i]>=0)
				e=1;
		}
		if(e)
			l=em;
		else r=em-1;
	}
	ll t=l;
	cout<<t;

}

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