제출 #309915

#제출 시각아이디문제언어결과실행 시간메모리
309915vipghn2003여행하는 상인 (APIO17_merchant)C++14
100 / 100
180 ms2296 KiB
#include <bits/stdc++.h> #define int long long template<typename T> void domax(T &a, T b) { if (b > a) a = b; } template<typename T> void domin(T &a, T b) { if (b < a) a = b; } using namespace std; const long long inf = 3e18, MaxT = 10ll*1000*1000; const int MaxN = 105, MaxK = 1005; int n, m, K; long long b[MaxN][MaxK], s[MaxN][MaxK], dist[MaxN][MaxN], best[MaxN][MaxN], cost[MaxN][MaxN]; bool can(long long eff) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][j] < inf) { cost[i][j] = best[i][j]-dist[i][j]*eff; } else { cost[i][j] = -inf; } } } for (int m = 0; m < n; m++) { for (int s = 0; s < n; s++) { for (int e = 0; e < n; e++) { domax(cost[s][e], cost[s][m] + cost[m][e]); if (cost[s][e] >inf) { cost[s][e] = inf; } } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (cost[i][j] + cost[j][i] >= 0) { return true; } } } return false; } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m>>K; for (int i = 0; i < n; i++) { for (int k = 0; k < K; k++) { cin>>b[i][k]>>s[i][k]; } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) dist[i][j]=3e18; } while(m--) { int u,v,w; cin>>u>>v>>w; u--; v--; dist[u][v]=w; } for(int u=0;u<n;u++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { int val=dist[i][u]+dist[u][j]; dist[i][j]=min(dist[i][j],val); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { best[i][j] = 0; // carrying no item for (int k = 0; k < K; k++) { if(b[i][k]==-1||s[j][k]==-1) continue; best[i][j]=max(best[i][j],s[j][k] - b[i][k]); } } } long long lo = 1ll, hi = 1000ll * 1000 * 1000; long long ans = 0ll; while (lo <= hi) { long long mid = (lo + hi) / 2; if (can(mid)) { lo = mid + 1; ans = mid; } else { hi = mid - 1; } } assert(!can(ans+1)); printf("%lld\n", ans); }

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

merchant.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...