Submission #135065

#	Time	Username	Problem	Language	Result	Execution time	Memory
135065		wzy	Travelling Merchant (APIO17_merchant)	C++11	0 / 100	45 ms	3448 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int K = 1005;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
#define pll pair<ll ,ll>
int n , m , k;
ll b[N][K] , s[N][K];
pll dist[N][N];
ll opt[N][N];
bool vis[N][N][K];
vector<int> adj[N];
bool has[N][N];
bool cmp(pll a , pll b){
	if(b.F == 0 && b.S == 0) return 1;
	return a.F*b.S >= a.S * b.F;
}

int32_t main(){
	scanf("%d%d%d" , &n , &m , &k);
	for(int i = 0 ; i < n; i++){
		for(int j = 0 ; j < k ; j++){
			scanf("%lld%lld" , &b[i][j], & s[i][j]);
			if(b[i][j] == -1){
				b[i][j] = (ll) 1e9 + (ll) 1e9;
			}
			if(s[i][j] == -1){
				s[i][j] = - (ll) 1e9 - (ll) 1e9;
			}
		}
		for(int j = 0 ; j < n; j ++){
			opt[i][j] = 0;
		}
	}
	for(int i = 0 ; i < n; i++){
		for(int j = 0 ; j < n ; j ++){
			for(int kx = 0 ; kx < k ; kx ++ ){
				opt[i][j] = max(opt[i][j] , -b[i][kx] + s[j][kx]);
			}
		}
	}

	for(int i = 0 ; i < N ; i ++){
		for(int j = 0 ; j < N ; j ++ ){
			dist[i][j] = pll(-(ll) 1e9,  (ll) 1e9 );
		}
		dist[i][i] = pll(0 , 0);
	}
	for(int i = 0 ; i < N ; i ++){
		for(int j = 0 ; j < N ; j ++){
			dist[i][j].F =  opt[i][j];
		}
	}
	for(int i = 0 ; i < m ; i ++){
		int  u , v, x;
		scanf("%d%d%d" , &u , & v  , &x);
		u-- , v--;
		assert(u >= 0 && v >= 0);
		has[u][v] = true;
		dist[u][v].S = min(dist[u][v].S , (ll) x);
	}
	for(int i = 0 ; i < n; i ++){
		for(int j = 0 ; j < n ; j ++){
			for(int kx = 0 ; kx < n; kx++){
				has[j][kx] |= has[j][i] & has[i][kx];
			}
		}
	}
	for(int i = 0 ; i < n; i ++ ){
		for(int j = 0 ; j < n ; j ++){
			for(int kx = 0 ; kx < n ; kx ++){
				if(cmp(pll(dist[j][i].F + dist[i][kx].F , dist[j][i].S + dist[i][kx].S) , dist[j][kx]) && has[j][i] && has[i][kx] && has[j][kx]){
					// cout<<j<<" "<<kx << endl;
					dist[j][kx] = pll(dist[j][i].F + dist[i][kx].F  , dist[j][i].S + dist[i][kx].S);
				}
			}
		}
	}
	long long int ans = 0;
	for(int i = 0 ; i < n; i ++){
		if(dist[i][i].S != 0){
			ans = max(ans , dist[i][i].F / dist[i][i].S);
		}
	}
	for(int i = 0 ; i < n; i ++){
		for(int j = 0 ; j < n; j ++){
			// cout<<i <<" " <<j <<" " << dist[i][j].first<<" " <<dist[i][j].second << endl;
		}
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

merchant.cpp: In function 'int32_t main()':
merchant.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d" , &n , &m , &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld" , &b[i][j], & s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &u , & v  , &x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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