Submission #1260184

#TimeUsernameProblemLanguageResultExecution timeMemory
1260184arashmemarTravelling Merchant (APIO17_merchant)C++20
0 / 100
199 ms2244 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 101, maxk = 1001; const long long int inf = 1e18; const long double e = ((long double)1) / (2 * maxn * maxn); long long int ine[maxn][maxn]; long long int ne[maxn][maxn]; long long int b[maxn][maxk], s[maxn][maxk]; long long int dis[maxn][maxn]; long double bel[maxn]; int n, k; bool solve(long long int x) { for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { ne[i][j] = inf; if (ine[i][j] < inf) { ne[i][j] = min(inf, ine[i][j] * x); } dis[i][j] = ne[i][j]; } } for (int i = 1;i <= n;i++) { dis[i][i] = 0; } for (int v = 1;v <= n;v++) { for (int u = 1;u <= n;u++) { for (int p = 1;p <= n;p++) { dis[v][u] = min(dis[v][u], dis[v][p] + dis[p][u]); } } } for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { if (j == i) { continue; } ne[i][j] = min(ne[i][j], dis[i][j]); for (int o = 1;o <= k;o++) { if (b[i][o] != inf and s[j][o] != inf) { ne[i][j] = min(ne[i][j], b[i][o] - s[j][o] + dis[i][j]); if (dis[i][j] + dis[j][i] <= -b[i][o] + s[j][o] and i == 1) { return 1; } } } } } return 0; for (int i = 1;i <= n;i++) { bel[i] = 0; } for (int i = 0;i < 2 * n;i++) { for (int v = 1;v <= n;v++) { for (int u = 1;u <= n;u++) { bel[u] = min(bel[u], bel[v] + ne[v][u] - e); } } } for (int v = 1;v <= n;v++) { for (int u = 1;u <= n;u++) { if (bel[u] > bel[v] + ne[v][u] - e) { return 1; } } } return 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); for (int i = 0;i < maxn;i++) { for (int j = 0;j < maxn;j++) { ine[i][j] = inf; } } int m; 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]; if (b[i][j] == -1) { b[i][j] = inf; } if (s[i][j] == -1) { s[i][j] = inf; } } } while (m--) { int v, u, w; cin >> v >> u >> w; ine[v][u] = w; } long long int l = 0, r = 1e9; while (r - l - 1) { long long int mid = (l + r) / 2; if (solve(mid)) { l = mid; } else { r = mid; } } cout << l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...