oj.uz

Submission #57387

# Submission time Handle Problem Language Result Execution time Memory
57387 2018-07-14T18:29:49 Z thiago4532 Travelling Merchant (APIO17_merchant) C++17
0 / 100
 88 ms 1592 KB 
#include <bits/stdc++.h>

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

bool check(int64_t eff){
	memset(g, 0x3f, sizeof g);

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dist[i][j] < inf) 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(1e9)+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], int64_t(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 Correct 88 ms 1400 KB Output is correct
2 Incorrect 60 ms 1508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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