제출 #956388

#제출 시각아이디문제언어결과실행 시간메모리
956388VMaksimoski008여행하는 상인 (APIO17_merchant)C++14
0 / 100
80 ms1480 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int P[505][505], n, m, K, i, j, k, a, b, c; int main() { cin >> n >> m >> K; vector<vector<ll> > M(n+1, vector<ll>(n+1, 1e16)); int B[n+1][K], S[n+1][K]; for(i=1; i<=n; i++) for(j=0; j<K; j++) cin >> B[i][j] >> S[i][j]; for(i=0; i<m; i++) { cin >> a >> b >> c; M[a][b] = min(M[a][b], 1ll * c); } auto F = [&](vector<vector<ll> > &D) { for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) D[i][j] = min(D[i][j], D[i][k] + D[k][j]); }; F(M); for(i=1; i<=n; i++) for(j=1; j<=n; j++) for(k=0; k<K; k++) if(S[j][k] != -1 && B[i][k] != -1) P[i][j] = max(P[i][j], S[j][k] - B[i][k]); ll l=1, r=1e7, ans=0; while(l <= r) { ll mid = (l + r) / 2; vector<vector<ll> > M2(n+1, vector<ll>(n+1, 1e16)); for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(M[i][j] < 1e16) M2[i][j] = mid * M[i][j] - P[i][j]; F(M2); bool ok = 0; for(i=1; i<=n; i++) if(M2[i][i] <= 0) ok = 1; if(ok) ans = mid, l = mid + 1; else r = mid - 1; } cout << ans << '\n'; 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...