Submission #660172

#	Time	Username	Problem	Language	Result	Execution time	Memory
660172		amir	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	141 ms	2012 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end() 
#define sz(x) (int)(x.size())
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'

struct E{
	ll u , v , w ;
};

const ll maxn = 103 , maxk = 1e3 + 4 , inf = 1e16 + 7 ;
ll n , m , k ;
ll s[maxn][maxn] , b[maxn][maxn] ;
ll c[maxn][maxn] , d[maxn][maxn];
vector<pll> adj[maxn] ;
vector<E> edge ;
ll dp[maxn] ;

bool get(ll ans){
	edge.clear() ;
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ; j < n ; j++){
			if (i == j) continue ;
			E e ;
			e.u = i , e.v = j , e.w = ((ans * d[i][j]) - c[i][j]) ;
			edge.ps(e) ;
		}
	}
	for (int i = 0; i < n; i++)
		dp[i] = inf ;
	dp[0] = 0 ;
	for (int cnt = 0; cnt < n ; cnt ++){
		for (E e : edge){
			ll u = e.u , v = e.v , w = e.w ;
			dp[v] = min(dp[v] , (dp[u] + w)) ;
		}
	}
	bool check = false ;
	for (E e : edge){
		ll u = e.u , v = e.v , w = e.w ;
		if (dp[v] > (dp[u] + w)){
			check = true ;
			break ;
		}
	}
	return check ;
}


int main()
{
    ios::sync_with_stdio(false) ; 
	cin.tie(NULL) ;
	cout.tie(NULL) ;
	cin >> n >> m >> k ;
	for (int i = 0 ; i < n; i++){
		for (int j = 0 ; j < k ; j++){
			ll ss , bb ;
			cin >> bb >> ss ;
			if (ss == -1) ss = 0-inf ;
			if (bb == -1) bb = inf ;
			s[i][j] = ss ; b[i][j] = bb ;
		}
	}
	for (int i = 0 ; i < m ; i++){
		ll u , v , t ;
		cin >> u >> v >> t ;
		u-- , v-- ;
		adj[u].ps(mp(v , t)) ;
	}
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ; j < n ; j++){
			for (int h = 0 ;h < k;  h++){
				c[i][j] = max(c[i][j] , (s[j][h] - b[i][h])) ;
			}
		}
	}
	for (int i = 0 ; i < n ; i++){
		for (pii j : adj[i]){
			d[i][j.first] = j.second ;
		}
	}
	for (int i = 0 ; i < n ; i++){
		for (int j = 0 ; j < n ; j++){
			if (!d[i][j])
				d[i][j] = inf ;
		}
	}
	for (int cnt = 0; cnt < n ; cnt ++){
		for (int i = 0 ; i < n; i++){
			for (int j = 0 ;j <= n ; j++)
				d[i][j] = min(d[i][j] , (d[i][cnt] + d[cnt][j])) ;
		}
	}
	ll l = 0  , r = 1e13 ;
	while (l < r-1){
		ll mid = (l + r) >> 1 ;
		if (get(mid)){
			l = mid + 1 ;
		}
		else
			r = mid + 1 ;
	}
	cout << l << '\n' ;
}

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