제출 #745114

#제출 시각아이디문제언어결과실행 시간메모리
745114Trunkty여행하는 상인 (APIO17_merchant)C++14
0 / 100
23 ms2260 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll int n,m,k; int store[105][1005][2]; int dist[105][105],prof[105][105]; int best[105][105][2]; signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ cin >> store[i][j][0] >> store[i][j][1]; if(store[i][j][0]==-1){ store[i][j][0] = 2e9; } if(store[i][j][1]==-1){ store[i][j][1] = -1; } } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i!=j){ dist[i][j] = 2e18; } } } for(int i=1;i<=m;i++){ int a,b,c; cin >> a >> b >> c; dist[a][b] = c; } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]); } } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ prof[i][j] = -2e9; for(int k=1;k<=n;k++){ prof[i][j] = max(prof[i][j],store[i][k][1]-store[j][k][0]); } } } /* for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout << dist[i][j] << " "; } cout << "\n"; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout << prof[i][j] << " "; } cout << "\n"; } */ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ best[i][j][0] = prof[i][j]; best[i][j][1] = dist[i][j]; } } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(best[i][j][1]==0){ best[i][j][0] = best[i][k][0]+best[k][j][0]; best[i][j][1] = best[i][k][1]+best[k][j][1]; } else{ if(best[i][k][1]+best[k][j][1]==0){ continue; } long double a = best[i][k][0]+best[k][j][0], b = best[i][k][1]+best[k][j][1], c = best[i][j][0], d = best[i][j][1]; if(a/b>c/d){ best[i][j][0] = a; best[i][j][1] = b; } } } } } int ans=0; for(int i=1;i<=n;i++){ if(best[i][i][1]){ ans = max(ans,best[i][i][0]/best[i][i][1]); } } cout << ans << "\n"; 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...