oj.uz

Submission #57384

# Submission time Handle Problem Language Result Execution time Memory
57384 2018-07-14T18:09:38 Z thiago4532 Travelling Merchant (APIO17_merchant) C++17
0 / 100
 140 ms 26456 KB 
#include <bits/stdc++.h>
#define int int64_t

using namespace std;
const int maxn = 1e3 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k, dist[maxn][maxn];
int b[maxn][maxn], s[maxn][maxn], e[maxn][maxn], g[maxn][maxn];

bool check(int eff){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			g[i][j] = eff*dist[i][j] - e[i][j];
		}
	}

	for(int l=1;l<=n;l++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				g[i][j] = min(g[i][j], g[i][l] + g[l][j]);
			}
		}
	}

	for(int i=1;i<=n;i++)
		if(g[i][i] <= 0) return true;

	return false;
}

int buscab(){
	int ini=1, fim=int(1e18)+1, meio;
	while(fim - ini > 1){
		meio = (ini+fim)>>1;
		if(check(meio))
			ini = meio;
		else
			fim = meio;
	}
	return ini;
}



int32_t main(){
	ios::sync_with_stdio(false), cin.tie(0);
	memset(dist, 0x3f, sizeof dist);
	memset(b, -1, sizeof b);
	memset(s, -1, sizeof s);

	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];
		}
	}	

	for(int i=1;i<=m;i++){
		int u, v, d;
		cin >> u >> v >> d;
		dist[u][v] = min(dist[u][v], d);
	}

	for(int l=1;l<=n;l++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);
			}
		}
	}

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int l=1;l<=k;l++){
				if(s[j][k] != -1 && b[i][k] != -1)
					e[i][j] = max(e[i][j], s[j][k] - b[i][k]);
			}
		}
	}

	cout << buscab() << "\n";
	return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 25720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 25720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 26456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 25720 KB Output isn't correct
2 Halted 0 ms 0 KB -