제출 #919403

#제출 시각아이디문제언어결과실행 시간메모리
919403vnm06여행하는 상인 (APIO17_merchant)C++14
100 / 100
120 ms4512 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; long long inf=4e18; long long n, m, K; long long b[105][1005], s[105][1005]; long long vreme[105][105]; long long val[105][105]; long long ed[105][105]; long long distc[105][105]; long long tek[105][105]; bool pos(long long x) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(vreme[i][j]!=inf) ed[i][j]=x*vreme[i][j]-val[i][j]; else ed[i][j]=inf; distc[i][j]=ed[i][j]; } } for(int i=1; i<=n; i++) distc[i][i]=0; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { tek[i][j]=distc[i][j]; } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) continue; if(distc[i][j]+distc[j][i]<=0) return 1; } } for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { if(distc[i][i]<0) return 1; for(int j=1; j<=n; j++) { if(distc[i][k]==inf || distc[k][j]==inf) continue; if(distc[i][k]+distc[k][j]<distc[i][j]) distc[i][j]=distc[i][k]+distc[k][j]; } } } for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(distc[i][k]==inf || distc[k][j]==inf) continue; if(distc[i][k]+distc[k][j]<distc[i][j]) return 1; } } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) continue; if(distc[i][j]+distc[j][i]<=0) return 1; } } return 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>K; for(int i=1; i<=n; i++) { for(int j=1; j<=K; j++) { cin>>b[i][j]>>s[i][j]; if(b[i][j]==-1) b[i][j]=inf; } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) vreme[i][j]=inf; vreme[i][i]=0; } for(int i=0; i<m; i++) { int u, v, d; cin>>u>>v>>d; vreme[u][v]=d; } for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(vreme[i][k]+vreme[k][j]<vreme[i][j]) vreme[i][j]=vreme[i][k]+vreme[k][j]; } } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { for(int t=1; t<=K; t++) if(val[i][j]<s[j][t]-b[i][t]) val[i][j]=s[j][t]-b[i][t]; } } long long le=0, ri=1e9+1; while(ri-le>1) { long long mid=(le+ri)/2; if(pos(mid)) le=mid; else ri=mid; } cout<<le<<endl; return 0; } /** 4 5 2 10 9 5 -1 6 4 20 -1 9 7 10 -1 -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...