제출 #945037

#제출 시각아이디문제언어결과실행 시간메모리
945037JakobZorz여행하는 상인 (APIO17_merchant)C++17
100 / 100
77 ms4252 KiB
#include<iostream> #include<vector> #include<queue> #include<stack> #include<algorithm> #include<limits.h> #include<math.h> #include<map> #include<set> #include<unordered_map> #include<unordered_set> #include<iomanip> #include<cstring> #include<random> typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; int n,m,k; ll buy[100][1000]; ll sell[100][1000]; ll profit[100][100]; ll dist[100][100]; ll cost[100][100]; void solve(){ cin>>n>>m>>k; for(int i=0;i<n;i++) for(int j=0;j<k;j++) cin>>buy[i][j]>>sell[i][j]; for(int i1=0;i1<n;i1++) for(int i2=0;i2<n;i2++) for(int j=0;j<k;j++) if(sell[i2][j]!=-1&&buy[i1][j]!=-1) profit[i1][i2]=max(profit[i1][i2],sell[i2][j]-buy[i1][j]); for(int i1=0;i1<n;i1++) for(int i2=0;i2<n;i2++) dist[i1][i2]=1e18; for(int i=0;i<m;i++){ int a,b,w; cin>>a>>b>>w; dist[a-1][b-1]=w; } for(int j=0;j<n;j++) for(int i1=0;i1<n;i1++) for(int i2=0;i2<n;i2++) dist[i1][i2]=min(dist[i1][i2],dist[i1][j]+dist[j][i2]); ll l=0,r=2e9; while(l<r-1){ ll curr=(l+r)/2; // does there exist a cycle with efficiency at least curr? for(int i1=0;i1<n;i1++) for(int i2=0;i2<n;i2++) cost[i1][i2]=curr*min(dist[i1][i2],ll(1e18)/curr)-profit[i1][i2]; for(int j=0;j<n;j++) for(int i1=0;i1<n;i1++) for(int i2=0;i2<n;i2++) cost[i1][i2]=min(cost[i1][i2],cost[i1][j]+cost[j][i2]); bool has=false; for(int i=0;i<n;i++) if(cost[i][i]<=0) has=true; if(has) l=curr; else r=curr; } cout<<l<<"\n"; } int main(){ ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL); //freopen("/Users/jakob/cp_testing/test.txt","r",stdin);freopen("output.out","w",stdout); int t=1;//cin>>t; while(t--)solve(); return 0; } /* 4 5 2 10 9 5 2 6 4 20 15 9 7 10 9 -1 -1 16 11 1 2 3 2 3 3 1 4 1 4 3 1 3 1 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...