제출 #657218

#제출 시각아이디문제언어결과실행 시간메모리
657218amirhoseinfar1385여행하는 상인 (APIO17_merchant)C++17
100 / 100
159 ms4140 KiB
#include<bits/stdc++.h> using namespace std; const long long maxn=102,maxm=9905,maxk=1001; long long inf=1e9+10; long long dis[maxn][maxn],cm[maxn][maxn],b[maxn][maxk],s[maxn][maxk]; long long n,m,k; void aval(){ for(long long i=0;i<n;i++){ for(long long j=0;j<n;j++){ for(long long h=0;h<k;h++){ if(b[i][h]==-1||s[j][h]==-1){ continue; } cm[i][j]=max(cm[i][j],s[j][h]-b[i][h]); } } } for(long long h=0;h<n;h++){ for(long long i=0;i<n;i++){ for(long long j=0;j<n;j++){ dis[i][j]=min(dis[i][j],dis[i][h]+dis[h][j]); } } } } bool check(long long mid){ vector<vector<long long>>fake(maxn,vector<long long>(maxn)); for(long long i=0;i<n;i++){ for(long long j=0;j<n;j++){ if(dis[i][j]>=inf){ fake[i][j]=-inf; } else{ fake[i][j]=cm[i][j]-mid*dis[i][j]; } } } for(long long h=0;h<n;h++){ for(long long i=0;i<n;i++){ for(long long j=0;j<n;j++){ if(fake[i][h]>=inf||fake[h][j]>=inf){ continue; } fake[i][j]=max(fake[i][j],fake[i][h]+fake[h][j]); } } } for(long long i=0;i<n;i++){ // if(mid==2){ // cout<<fake[i][i]<<endl; // } if(fake[i][i]>=0){ return 1; } } return 0; } int main(){ cin>>n>>m>>k; for(long long i=0;i<n;i++){ for(long long j=0;j<k;j++){ cin>>b[i][j]>>s[i][j]; } } for(long long i=0;i<maxn;i++){ for(long long j=0;j<maxn;j++){ dis[i][j]=inf; } } for(long long i=0;i<m;i++){ long long u,v,w; cin>>u>>v>>w; u--; v--; dis[u][v]=min(w,dis[u][v]); } // cout<<s[0][1]<<" "<<b[2][1]<<endl; aval(); // cout<<dis[0][2]<<" "<<dis[2][0]<<" "<<cm[0][2]<<" "<<cm[2][0]<<endl; long long low=0,high=1e9+20,mid; while(high-low>1){ mid=(high+low)>>1; if(check(mid)){ low=mid; } else{ high=mid; } } cout<<low<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...