Submission #411687

#	Time	Username	Problem	Language	Result	Execution time	Memory
411687		soroush	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	194 ms	4612 KiB

merchant

//叫んで 藻掻もがいて 瞼まぶたを腫らしても
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 110;
const int maxk = 1010;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m , k;
int b[maxn][maxk] , s[maxn][maxk];
vector < pii > adj[maxn];

int dist[maxn][maxn] , mx[maxn][maxn];

ll w[maxn][maxn];
ll f[maxn][maxn];
ll d[maxn];

bool chk(ll x){
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= n ; j ++)if(dist[i][j] != dist[0][0])
			w[i][j] = -(mx[i][j] - dist[i][j] * x);
		else
			w[i][j] = 1e15;
	ms(d , 63);
	d[1] = 0;
	if(0){
		for(int i = 1 ; i <= n ; i ++ , cout << endl)
			for(int j = 1 ; j <= n ; j ++)
				cout << w[i][j] << ' ' ;
	}
	for(int i = 1 ; i < n ; i ++)
		for(int j = 1 ; j <= n ; j ++)
			for(int k = 1 ; k <= n ; k ++)
				if(d[j] < 1e18 - w[j][k])
					d[k] = min(d[k] , d[j] + w[j][k]); 
	for(int j = 1 ; j <= n ; j ++)
		for(int k = 1 ; k <= n ; k ++)if(k ^ j)
			if(d[j] < 1e18 - w[j][k] and d[k] > d[j] + w[j][k])
				return 1;
	ms(f , 63);
	for(int i = 1 ; i <= n ; i ++)f[i][i] = 0;
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= n ; j ++)
			f[i][j] = min(f[i][j] , w[i][j]);
	for(int k = 1 ; k <= n ; k ++)
		for(int i = 1 ; i <= n ; i ++)
			for(int j = 1 ; j <= n ; j ++)
				if(f[i][k] != f[0][0] and f[k][j] != f[0][0])
					f[i][j] = min(f[i][j] , f[i][k] + f[k][j]);
	for(int i = 1 ; i <= n ; i ++)
		for(int j = i+1 ; j <= n; j ++)
			if(f[i][j] + f[j][i] == 0)
				return  1;
	return 0;
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	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];
	ms(dist , 63);
	for(int i = 1 ; i <= n ; i ++) dist[i][i] = 0;
	for(int i = 1 ; i <= m ; i ++){
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].pb({v , w});
		dist[u][v] = min(dist[u][v] , w);
	}
	for(int k = 1 ; k <= n ; k ++)
		for(int i = 1 ; i <= n ; i ++)
			for(int j = 1 ; j <= n ; j ++)
				if(dist[i][k] != dist[0][0] and dist[k][j] != dist[0][0])
					dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= n ; j ++) if(j ^ i)
			for(int l = 1 ; l <= k ; l ++) if(s[j][l] != -1 and b[i][l] != -1)
				mx[i][j] = max(mx[i][j] , s[j][l] - b[i][l]);
	ll l = 0 , r = 1e10;
	while(r - l > 1){
		ll mid = (l + r) / 2;
		if(chk(mid))l = mid;
		else r = mid;
	}
	cout << l;
	return(0);
}

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