제출 #106228

#제출 시각아이디문제언어결과실행 시간메모리
106228polyfish여행하는 상인 (APIO17_merchant)C++14
33 / 100
1055 ms3292 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 int64_t _EPS = 1e-8; struct edge { int64_t u, v; int64_t w; edge() {} edge(int64_t u, int64_t v, int64_t 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]; int64_t 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 detect_zero_cycle(int u, int root) { // debug(u); for (auto e : g[u]) { if (abs(d[e.v]-d[u]-e.w)<=_EPS && (e.v==root || detect_zero_cycle(e.v, root))) return true; } return false; } bool check_negative_cycle(int64_t x) { vector<edge> E; for (int64_t i=1; i<=n; ++i) { g[i].clear(); for (int64_t j=1; j<=n; ++j) { // if (i==4 && j==1) // debug(x*c[i][j] - max((int64_t)0, mx[i][j])); if (i!=j) { E.push_back(edge(i, j, x*c[i][j] - max((int64_t)0, mx[i][j]))); g[i].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; } // debug(detect_zero_cycle(1, 1)); for (int i=1; i<=n; ++i) { if (detect_zero_cycle(i, i)) { // debug(i); return true; } } return false; } int64_t bisect() { int64_t l = 0, r = INF; for (int64_t mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) { if (check_negative_cycle(mid)) l = mid; else r = mid; } for (int64_t i=r; i>=l; --i) { if (check_negative_cycle(i)) return i; } return 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); read_input(); floyd(); init(); // debug(check_negative_cycle(2)); cout << int64_t(bisect()); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...