제출 #842171

#제출 시각아이디문제언어결과실행 시간메모리
842171Tob여행하는 상인 (APIO17_merchant)C++14
100 / 100
81 ms4332 KiB
#include <bits/stdc++.h> #define ll long long #define F first #define S second #define all(x) x.begin(), x.end() #define pb push_back #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef pair <ll, ll> pii; const int N = 107, K = 1007; const ll inf = 1e18; int n, m, k; ll b[N][K], s[N][K], d[N][N], pr[N][N], dis[N][N]; void Min(ll& x, ll y) {x = min(x, y);} void Max(ll& x, ll y) {x = max(x, y);} int main () { FIO; cin >> n >> m >> k; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = inf; for (int i = 1; i <= n; i++) { d[i][i] = 0; for (int j = 1; j <= k; j++) { cin >> b[i][j] >> s[i][j]; } } for (int i = 1; i <= m; i++) { ll x, y, w; cin >> x >> y >> w; d[x][y] = w; } for (int ii = 1; ii <= n; ii++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { Min(d[i][j], d[i][ii] + d[ii][j]); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (d[i][j] == inf) continue; pr[i][j] = 0; for (int ii = 1; ii <= k; ii++) { if (b[i][ii] != -1 && s[j][ii] != -1) Max(pr[i][j], s[j][ii] - b[i][ii]); } } } ll lo = 0, hi = 1e9; while (lo < hi) { ll mid = (lo + hi + 1) / 2; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (d[i][j] == inf || i == j) dis[i][j] = inf; else dis[i][j] = -pr[i][j] + d[i][j] * mid; } } for (int ii = 1; ii <= n; ii++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { Min(dis[i][j], dis[i][ii] + dis[ii][j]); } } } int ok = 0; for (int i = 1; i <= n; i++) { ok |= (dis[i][i] <= 0); } if (ok) lo = mid; else hi = mid-1; } cout << lo << "\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...