제출 #583202

#제출 시각아이디문제언어결과실행 시간메모리
583202Jomnoi여행하는 상인 (APIO17_merchant)C++17
100 / 100
93 ms4176 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 105; const int MAX_K = 1005; const long long llINF = 1e18 + 7; long long B[MAX_N][MAX_K], S[MAX_N][MAX_K]; long long dist[MAX_N][MAX_N], dist2[MAX_N][MAX_N]; long long profit[MAX_N][MAX_N]; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N, M, K; cin >> N >> M >> K; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { dist[i][j] = llINF; } } for(int i = 1; i <= N; i++) { for(int k = 1; k <= K; k++) { cin >> B[i][k] >> S[i][k]; } } while(M--) { int v, w, t; cin >> v >> w >> t; dist[v][w] = t; } for(int k = 1; k <= N; k++) { for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { for(int k = 1; k <= K; k++) { if(B[i][k] != -1 and S[j][k] != -1) { profit[i][j] = max(profit[i][j], S[j][k] - B[i][k]); } } } } int l = 1, r = 1e9, ans = 0; while(l <= r) { int mid = (l + r) / 2; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { dist2[i][j] = llINF; if(dist[i][j] != llINF) { dist2[i][j] = dist[i][j] * mid - profit[i][j]; } } } for(int k = 1; k <= N; k++) { for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { dist2[i][j] = min(dist2[i][j], dist2[i][k] + dist2[k][j]); } } } bool hasNegCycle = false; for(int i = 1; i <= N; i++) { if(dist2[i][i] <= 0) { hasNegCycle = true; } } if(hasNegCycle == true) { l = mid + 1; ans = mid; } else { r = mid - 1; } } cout << ans; 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...