제출 #128374

#제출 시각아이디문제언어결과실행 시간메모리
128374keko37여행하는 상인 (APIO17_merchant)C++14
66 / 100
175 ms4216 KiB
#include<bits/stdc++.h> using namespace std; typedef long long llint; const int MAXN = 105; const int MAXP = 1005; const llint INF = 1000000007LL; llint n, m, p; llint buy[MAXN][MAXP], sell[MAXN][MAXP]; llint d[MAXN][MAXN], g[MAXN][MAXN]; llint cost[MAXN][MAXN]; void ispis () { for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { cout << g[i][j] << " "; } cout << endl; } } bool moze (llint t) { if (t == 0) return 1; for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { cost[i][j] = t * d[i][j] - g[i][j]; } } for (int k=1; k<=n; k++) { for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { if (cost[i][k] + cost[k][j] < cost[i][j]) { cost[i][j] = cost[i][k] + cost[k][j]; } if (cost[i][j] < -INF*INF) cost[i][j] = -INF*INF; } } } for (int i=1; i<=n; i++) { if (cost[i][i] <= 0) return 1; } return 0; } void precompute () { for (int k=1; k<=n; k++) { for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; } } } } for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { llint res = 0; for (int k=1; k<=p; k++) { res = max(res, sell[j][k] - buy[i][k]); } g[i][j] = res; } } } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> p; for (int i=1; i<=n; i++) { for (int j=1; j<=p; j++) { cin >> buy[i][j] >> sell[i][j]; if (buy[i][j] == -1) buy[i][j] = INF; if (sell[i][j] == -1) sell[i][j] = -INF; } } for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { d[i][j] = INF; } } for (int i=1; i<=m; i++) { int a, b, c; cin >> a >> b >> c; d[a][b] = c; } precompute(); llint lo = 0, hi = 1000000001; while (lo < hi) { llint mid = (lo + hi + 1) / 2; if (moze(mid)) { lo = mid; } else { hi = mid-1; } } cout << lo; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...