제출 #106227

#제출 시각아이디문제언어결과실행 시간메모리
106227polyfish여행하는 상인 (APIO17_merchant)C++14
54 / 100
301 ms3188 KiB
//Pantyhose(black) + glasses = infinity #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "merchant" const int64_t MAX_N = 102; const int64_t MAX_K = 1002; const int64_t INF = 1e9+1e8; const long double _EPS = 1e-8; struct edge { int64_t u, v; long double w; edge() {} edge(int64_t u, int64_t v, long double w): u(u), v(v), w(w) {} }; int64_t n, m, k, b[MAX_N][MAX_K], s[MAX_N][MAX_K], c[MAX_N][MAX_N], mx[MAX_N][MAX_N]; vector<edge> g[MAX_N]; long double d[MAX_N]; void read_input() { cin >> n >> m >> k; for (int64_t i=1; i<=n; ++i) { for (int64_t j=1; j<=k; ++j) cin >> b[i][j] >> s[i][j]; } } void floyd() { for (int64_t i=1; i<=n; ++i) { for (int64_t j=1; j<=n; ++j) c[i][j] = INF; } for (int64_t i=1; i<=n; ++i) c[i][i] = 0; for (int64_t i=1; i<=m; ++i) { int64_t u, v; cin >> u >> v; cin >> c[u][v]; } for (int64_t k=1; k<=n; ++k) { for (int64_t i=1; i<=n; ++i) { for (int64_t j=1; j<=n; ++j) c[i][j] = min(c[i][j], c[i][k] + c[k][j]); } } // debug(c[4][1]); } void init() { for (int64_t i=1; i<=n; ++i) { for (int64_t j=1; j<=n; ++j) { mx[i][j] = -INF; for (int64_t t=1; t<=k; ++t) { if (b[i][t]!=-1 && s[j][t]!=-1) mx[i][j] = max(mx[i][j], -b[i][t] + s[j][t]); } } } // debug(mx[1][4]); } bool relax(edge e) { if (abs(d[e.v] - d[e.u] - e.w)>_EPS && d[e.v] > d[e.u] + e.w) { d[e.v] = d[e.u] + e.w; return true; } return false; } bool check_negative_cycle(long double x) { vector<edge> E; for (int64_t i=1; i<=n; ++i) { for (int64_t j=1; j<=n; ++j) E.push_back(edge(i, j, x*c[i][j] - max((int64_t)0, mx[i][j]))); } memset(d, 0, sizeof(d)); for (int64_t i=0; i<=n; ++i) { if (i==n) return true; bool stop = true; for (auto e : E) { if (relax(e)) stop = false; } if (stop) break; } return false; } long double bisect() { long double l = 0, r = INF; while (abs(l-r)>1e-6) { long double mid = (l + r) / 2; if (check_negative_cycle(mid)) l = mid; else r = mid; } // cerr << setiosflags(ios::fixed) << setprecision(7) << l << '\n'; return r; } int main() { ios::sync_with_stdio(0); cin.tie(0); read_input(); floyd(); init(); // debug(check_negative_cycle(1.9)); cout << int64_t(bisect()); // for (int64_t i=1; i<=n; ++i) { // for (int64_t j=1; j<=n; ++j) { // if (mx[i][j]==-INF) // cout << -1 << " \n"[j==n]; // else // cout << mx[i][j] << " \n"[j==n]; // } // } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...