제출 #1198348

#제출 시각아이디문제언어결과실행 시간메모리
1198348ivaziva여행하는 상인 (APIO17_merchant)C++20
0 / 100
65 ms2112 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 101 #define MAXM 1001 #define int long long int n,m,k; int buy[MAXN][MAXM],sell[MAXN][MAXM]; int adj[2][MAXN][MAXN],profit[MAXN][MAXN]; bool check(int mid) { for (int node1=1;node1<=n;node1++) { for (int node2=1;node2<=n;node2++) adj[1][node1][node2]=mid*min(adj[0][node1][node2],LLONG_MAX/mid)-profit[node1][node2]; } for (int node=1;node<=n;node++) { for (int node1=1;node1<=n;node1++) { for (int node2=1;node2<=n;node2++) { if (adj[1][node1][node]==LLONG_MAX or adj[1][node][node2]==LLONG_MAX) continue; adj[1][node1][node2]=min(adj[1][node1][node2],adj[1][node1][node]+adj[1][node][node2]); } } } for (int node=0;node<=n;node++) { if (adj[1][node][node]<0) return false; } return true; } int32_t main() { cin>>n>>m>>k; for (int node=1;node<=n;node++) { for (int item=1;item<=k;item++) cin>>buy[node][item]>>sell[node][item]; for (int sled=1;sled<=n;sled++) adj[0][node][sled]=LLONG_MAX; } for (int i=1;i<=m;i++) {int node1,node2,time;cin>>node1>>node2>>time;adj[0][node1][node2]=time;} for (int node=1;node<=n;node++) { for (int node1=1;node1<=n;node1++) { for (int node2=1;node2<=n;node2++) { if (adj[0][node1][node]==LLONG_MAX or adj[0][node][node2]==LLONG_MAX) continue; adj[0][node1][node2]=min(adj[0][node1][node2],adj[0][node1][node]+adj[0][node][node2]); } } } for (int node1=1;node1<=n;node1++) { for (int node2=1;node2<=n;node2++) { for (int item=1;item<=k;item++) { if (buy[node1][item]==-1 or sell[node2][item]==-1) continue; profit[node1][node2]=max(profit[node1][node2],sell[node2][item]-buy[node1][item]); } } } int l=1,r=INT_MAX,rez=0; while (l<=r) { int mid=(l+r)/2; if (check(mid)) {rez=mid;r=mid-1;} else l=mid+1; } cout<<rez<<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...