제출 #620241

#제출 시각아이디문제언어결과실행 시간메모리
620241GusterGoose27여행하는 상인 (APIO17_merchant)C++11
100 / 100
146 ms3484 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef long double ld; const int MAXN = 100; const int MAXK = 1000; const ll inf = 1e18; const ld ERROR = 1e-9; int n, m, k; vector<pii> edges[MAXN]; ll dist[MAXN][MAXN]; ld bfdist[MAXN]; int val[MAXN][MAXN]; int buy[MAXN][MAXK]; int sell[MAXN][MAXK]; bool neg_cycle(ld ben) { fill(bfdist, bfdist+n, inf); bfdist[0] = 0; bool f = 1; for (int i = 0; i < n && f; i++) { f = 0; for (int a = 0; a < n; a++) { for (int b = 0; b < n; b++) { ld w = ben*dist[a][b]-val[a][b]; if (bfdist[b] > bfdist[a]+w+ERROR) { bfdist[b] = bfdist[a]+w; f = 1; } } } } return f; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { cin >> buy[i][j]; cin >> sell[i][j]; } fill(dist[i], dist[i]+n, inf); dist[i][i] = 0; } for (int i = 0; i < m; i++) { int x, y, w; cin >> x >> y >> w; x--; y--; edges[x].push_back(pii(y, w)); dist[x][y] = w; } for (int i = 0; i < n; i++) { for (int a = 0; a < n; a++) { for (int b = 0; b < n; b++) dist[a][b] = min(dist[a][b], dist[a][i]+dist[i][b]); } } for (int a = 0; a < n; a++) { for (int b = 0; b < n; b++) { for (int i = 0; i < k; i++) { if (buy[a][i] != -1 && sell[b][i] != -1) val[a][b] = max(val[a][b], sell[b][i]-buy[a][i]); } } } int mn = 0; int mx = 1e9; while (mx > mn+1) { int cur = (mn+mx)/2; if (neg_cycle(cur-ERROR)) mn = cur; else mx = cur; } cout << mn << "\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...