Submission #1034495

#TimeUsernameProblemLanguageResultExecution timeMemory
1034495andrei_iorgulescu여행하는 상인 (APIO17_merchant)C++14
100 / 100
975 ms8220 KiB
#include <bits/stdc++.h> using namespace std; using ld = long double; using ll = long long; ld eps = 0.00000000001d; int n,m,k; int b[105][1005],s[105][1005]; int d[105][105][105]; int f[105][105]; ld cost[105][105]; vector<pair<int,ld>> g[105]; bool inq[105]; int nrq[105]; ld dist[105]; bool ciclu_negativ() { queue<int> q; for (int i = 1; i <= n; i++) inq[i] = true,nrq[i] = 1,dist[i] = 0,q.push(i); while (!q.empty()) { int nod = q.front(); q.pop(); inq[nod] = false; for (auto vecin : g[nod]) { if (dist[vecin.first] > dist[nod] + vecin.second) { dist[vecin.first] = dist[nod] + vecin.second; if (!inq[vecin.first]) { inq[vecin.first] = true; nrq[vecin.first]++; q.push(vecin.first); if (nrq[vecin.first] > 1000) return true; } } } } return false; } bool pot(int t) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cost[i][j] = (f[i][j] / (ld)t) - (ld)d[n][i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cost[i][j] = -cost[i][j] - eps; for (int i = 1; i <= n; i++) { g[i].clear(); for (int j = 1; j <= n; j++) if (i != j and d[n][i][j] != -1) g[i].push_back({j,cost[i][j]}); } return ciclu_negativ(); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 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 <= n; i++) for (int j = 1; j <= n; j++) for (int ii = 0; ii <= n; ii++) d[ii][i][j] = -1; for (int i = 1; i <= n; i++) d[0][i][i] = 0; for (int i = 1; i <= m; i++) { int x,y,cost; cin >> x >> y >> cost; d[0][x][y] = cost; } for (int kk = 1; kk <= n; kk++) { for (int x = 1; x <= n; x++) { for (int y = 1; y <= n; y++) { if (x == y) d[kk][x][y] = 0; else { d[kk][x][y] = d[kk - 1][x][y]; if (d[kk - 1][x][kk] != -1 and d[kk - 1][kk][y] != -1) if (d[kk - 1][x][kk] + d[kk - 1][kk][y] < d[kk][x][y] or d[kk][x][y] == -1) d[kk][x][y] = d[kk - 1][x][kk] + d[kk - 1][kk][y]; } } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != j) { for (int q = 1; q <= k; q++) { if (b[i][q] != -1 and s[j][q] != -1) f[i][j] = max(f[i][j],s[j][q] - b[i][q]); } } } } int st = 0, pas = 1 << 29; while (pas != 0) { if (pot(st + pas)) st += pas; pas /= 2; } cout << st; return 0; } /** Fie f(i,j) = practic costul maxim pe care il fac mergand de la i la j (direct route), L(i,j) = lungimea drumului L(i,j) calculez in n^3 cu floyd, f(i,j) in n^2k Caut binar raspunsul, sa zicem ca incerc >= T. f(i,j) /= T, f(i,j) -= L(i,j), f(i,j) = -f(i,j), f(i,j) -= 0.0000001. Acum doar caut un ciclu negativ Pentru asta, bellman-ford si am O(B * log), unde B este bellman ford-ul care parca era bounded by N * M deci N^3log pe worst case **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...