제출 #230561

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

merchant

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define upd(x, y) x=min(x, y)

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=20000000000000010LL;
const int mod=1000000007;
const int MAXN=110, MAXK=1010;

ll n, m, k, u, v, x, y, t, a, b, ans;
ll G[MAXN][MAXN], val[MAXN][MAXN];
ll B[MAXN][MAXK], S[MAXN][MAXK];
ll G2[MAXN][MAXN], dist[MAXN];

inline ll _mul(ll x, ll y){
	if (INF/x<y+5) return INF;
	return x*y;
}

bool check(ll x){
	//memset(G2, 0, sizeof(G2));
	for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) G2[i][j]=_mul(x, G[i][j])-val[i][j];
	//cerr<<"G2:\n";for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cerr<<G2[i][j]<<" \n"[j==n];cerr<<'\n';
	
	memset(dist, 63, sizeof(dist));
	dist[1]=0;
	for (int shit=1; shit<=n; shit++){
		for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (G[i][j]<=inf){
			ll d=dist[i]+G2[i][j];
			if (d<dist[j]){
				dist[j]=d;
				if (shit==n) return 1;
			}
		}
	}
	// pas dor manfi nadarim!
	
	for (int x=1; x<=n; x++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) upd(G2[i][j], G2[i][x]+G2[x][j]);
	for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (i!=j && G[i][j]<=inf && G2[j][i]+G2[i][j]<=0) return 1;
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	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];
	}
	
	memset(G, 63, sizeof(G));
	for (int i=1; i<=n; i++) G[i][i]=0;
	while (m--){
		cin>>u>>v>>x;
		upd(G[u][v], x);
	}
	for (int x=1; x<=n; x++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) upd(G[i][j], G[i][x]+G[x][j]);
	for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int x=1; x<=k; x++)
		if (B[i][x]!=-1 && S[j][x]!=-1) val[i][j]=max(val[i][j], S[j][x]-B[i][x]);
	
	//cerr<<"val:\n";for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cerr<<val[i][j]<<" \n"[j==n];cerr<<'\n';
	/*
	debug(check(2))
	return 0;
	*/
	
	int dwn=0, up=inf;
	while (up-dwn>1){
		int mid=(dwn+up)>>1;
		if (check(mid)) dwn=mid;
		else up=mid;
	}
	cout<<dwn<<'\n';
	
	return 0;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

*/

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