Submission #488117

#	Time	Username	Problem	Language	Result	Execution time	Memory
488117		S2speed	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	60 ms	2428 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 1e2 + 16 , maxk = 1e3 + 16 , md = 1e9 + 7 , inf = 1e10;

ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll n , m , k;
ll w[maxn][maxn] , dis[maxn][maxn] , a[maxn][maxk] ,  b[maxn][maxk] , f[maxn][maxn];
vector<pll> adj[maxn];
priority_queue<pll , vector<pll> , greater<pll>> pq;

void dij(ll r){
	pq.push({dis[r][r] = 0 , r});
	while(!pq.empty()){
		pll q = pq.top(); pq.pop();
		if(dis[r][q.second] != q.first) continue;
		ll v = q.second;
		for(auto p : adj[v]){
			ll i = p.first , w = p.second;
			if(dis[r][i] > dis[r][v] + w){
				dis[r][i] = dis[r][v] + w;
				pq.push({dis[r][i] , i});
			}
		}
	}
	return;
}

bool check(ll x){
	for(ll i = 0 ; i < n ; i++){
		for(ll j = 0 ; j < n ; j++){
			f[i][j] = 1ll * x * dis[i][j] - w[i][j];
		}
		f[i][i] = inf;
	}
	for(ll k = 0 ; k < n ; k++){
		for(ll i = 0 ; i < n ; i++){
			for(ll j = 0 ; j < n ; j++){
				if(f[i][k] < inf) f[i][j] = min(f[i][j] , f[i][k] + f[k][j]);
			}
		}
	}
	for(ll i = 0 ; i < n ; i++){
		if(f[i][i] <= 0) return true;
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin>>n>>m>>k;
	for(ll i = 0 ; i < n ; i++){
		for(ll j = 0 ; j < k ; j++){
			cin>>a[i][j]>>b[i][j];
		}
	}
	for(ll i = 0 ; i < n ; i++){
		for(ll j = 0 ; j < n ; j++){
			ll h = 0;
			for(ll q = 0 ; q < k ; q++){
				if(b[j][q] != -1 && a[i][q] != -1) h = max(h , b[j][q] - a[i][q]);
			}
			w[i][j] = h;
			dis[i][j] = inf;
		}
	}
	for(ll i = 0 ; i < m ; i++){
		ll v , u , w;
		cin>>v>>u>>w; v--; u--;
		adj[v].push_back({u , w});
	}
	for(ll i = 0 ; i < n ; i++){
		dij(i);
	}
	ll l = 0 , r = 1e9 + 112;
	while(l < r - 1){
		ll m = (r + l) >> 1;
		if(check(m)){
			l = m;
		} else {
			r = m;
		}
	}
	cout<<l<<'\n';
	return 0;
}

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