제출 #1073192

#제출 시각아이디문제언어결과실행 시간메모리
1073192alexdd여행하는 상인 (APIO17_merchant)C++17
33 / 100
81 ms5200 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; int n,m,k; int buy[105][1005],sell[105][1005]; int dist[105][105],profit[105][105],dist2[105][105]; bool verif(int lun) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist2[i][j] = min(INF/lun,dist[i][j])*lun - profit[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int q=1;q<=n;q++) dist2[i][q] = min(dist2[i][q], dist2[i][j] + dist2[j][q]); for(int i=1;i<=n;i++) if(dist2[i][i]<=0) return 1; return 0; } signed main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) cin>>buy[i][j]>>sell[i][j]; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dist[i][j]=INF; for(int q=1;q<=k;q++) if(buy[i][q]!=-1 && sell[j][q]!=-1) profit[i][j] = max(profit[i][j], sell[j][q] - buy[i][q]); } } int u,v,w; for(int i=1;i<=m;i++) { cin>>u>>v>>w; dist[u][v]=w; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int q=1;q<=n;q++) dist[i][q] = min(dist[i][q], dist[i][j] + dist[j][q]); int st=0,dr=1e9,ans=0; while(st<=dr) { int mij=(st+dr)/2; if(verif(mij)) { ans=mij; st=mij+1; } else dr=mij-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...