제출 #914596

#제출 시각아이디문제언어결과실행 시간메모리
914596dsyz여행하는 상인 (APIO17_merchant)C++17
100 / 100
66 ms4340 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define MAXN (1000005) ll N,M,K; ll buy[105][1005], sell[105][1005]; ll profit[105][105], graph1[105][105], graph2[105][105]; int main() { ios_base::sync_with_stdio(false);cin.tie(0); cin>>N>>M>>K; for(ll i = 0;i < N;i++){ for(ll j = 0;j < N;j++){ graph1[i][j] = 1e18; } } for(ll i = 0;i < N;i++){ for(ll j = 0;j < K;j++){ cin>>buy[i][j]>>sell[i][j]; //if buy[i][j] or sell[i][j] = -1 that means type j item cannot be bought/sold respectively at node i } } for(ll i = 0;i < M;i++){ ll a,b,c; cin>>a>>b>>c; a--, b--; graph1[a][b] = c; //directed edge from a to b with weight c } for(ll k = 0;k < N;k++){ for(ll i = 0;i < N;i++){ for(ll j = 0;j < N;j++){ graph1[i][j] = min(graph1[i][j],graph1[i][k] + graph1[k][j]); } } } for(ll i = 0;i < N;i++){ for(ll j = 0;j < N;j++){ for(ll k = 0;k < K;k++){ //note that this is not floyd warshall, just normal nested for loops to loop though buy[node i][item type k] and sell[node j][item type k] if(buy[i][k] != -1 && sell[j][k] != -1){ profit[i][j] = max(profit[i][j],sell[j][k] - buy[i][k]); //if we buy at node i and then sell at node j, we can keep on buying the same type of most optimal item since there is infinite stock of the same type } } } } ll high = 1e9 + 5; ll low = 0; while(high - low > 1){ ll mid = (high + low) / 2; for(ll i = 0;i < N;i++){ for(ll j = 0;j < N;j++){ if(graph1[i][j] >= 1e18) graph2[i][j] = 1e18 - profit[i][j]; else graph2[i][j] = (mid * graph1[i][j]) - profit[i][j]; } } for(ll k = 0;k < N;k++){ for(ll i = 0;i < N;i++){ for(ll j = 0;j < N;j++){ graph2[i][j] = min(graph2[i][j],graph2[i][k] + graph2[k][j]); } } } bool hasnegativecycle = false; for(ll i = 0;i < N;i++){ if(graph2[i][i] <= 0){ hasnegativecycle = true; } } if(hasnegativecycle){ low = mid; }else{ high = mid; } } cout<<low<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...