제출 #739391

#제출 시각아이디문제언어결과실행 시간메모리
739391Magikarp4000여행하는 상인 (APIO17_merchant)C++17
100 / 100
95 ms2160 KiB
#include <bits/stdc++.h> using namespace std; #define OPTM ios_base::sync_with_stdio(0); cin.tie(0); #define INF int(1e9+7) #define ln '\n' #define ll long long #define ull unsigned long long #define ui unsigned int #define us unsigned short #define FOR(i,s,n) for (int i = s; i < n; i++) #define FORR(i,n,s) for (int i = n; i > s; i--) #define FORX(u, arr) for (auto u : arr) #define PB push_back #define in(v,x) (v.find(x) != v.end()) #define F first #define S second #define PII pair<int, int> #define PLL pair<ll, ll> #define UM unordered_map #define US unordered_set #define PQ priority_queue #define ALL(v) v.begin(), v.end() const ll LLINF = 1e18+1; #define int long long const int MAXN = 1e2+1, MAXK = 1e3+1; int n,m,K; int b[MAXN][MAXK], s[MAXN][MAXK]; int dist[MAXN][MAXN], d[MAXN][MAXN], prof[MAXN][MAXN]; bool check(int val) { FOR(i,1,n+1) { FOR(j,1,n+1) { d[i][j] = LLINF; } } FOR(i,1,n+1) { FOR(j,1,n+1) { if (dist[i][j] == LLINF) continue; if (i == j || dist[i][j] == LLINF) continue; d[i][j] = dist[i][j]*val-prof[i][j]; } } FOR(k,1,n+1) { FOR(i,1,n+1) { FOR(j,1,n+1) { d[i][j] = min(d[i][j], d[i][k]+d[k][j]); } } } FOR(i,1,n+1) if (d[i][i] <= 0) return 1; return 0; } signed main() { OPTM; cin >> n >> m >> K; FOR(i,1,n+1) { FOR(j,1,K+1) cin >> b[i][j] >> s[i][j]; } FOR(i,1,n+1) { FOR(j,1,n+1) { dist[i][j] = LLINF; } } FOR(i,0,m) { int x,y,w; cin >> x >> y >> w; int mx = 0; FOR(j,1,K+1) dist[x][y] = w; } FOR(k,1,n+1) { FOR(i,1,n+1) { FOR(j,1,n+1) { dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]); } } } FOR(i,1,n+1) { FOR(j,1,n+1) { FOR(x,1,K+1) { if (dist[i][j] == LLINF) continue; if (s[j][x] != -1 && b[i][x] != -1) prof[i][j] = max(prof[i][j], s[j][x]-b[i][x]); } } } int l = 1, r = 1LL*(1e9+1); while (l < r) { int mid = (l+r)/2; if (check(mid)) l = mid+1; else r = mid; } cout << l-1; }

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp: In function 'int main()':
merchant.cpp:68:13: warning: unused variable 'mx' [-Wunused-variable]
   68 |         int mx = 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...