제출 #734759

#제출 시각아이디문제언어결과실행 시간메모리
734759bin9638여행하는 상인 (APIO17_merchant)C++17
100 / 100
121 ms20740 KiB
#include <bits/stdc++.h> using namespace std; #define N 1010 #define ll long long #define fs first #define sc second #define ii pair<ll,int> #define pb push_back #define int ll int n,m,k,buy[N][N],sell[N][N],cost[N][N],dis[N][N],ktr[N][N]; vector<ii>g[N]; ll get_cost(int u,int v) { ll res=-1e18; for(int i=1;i<=k;i++) if(buy[u][i]!=-1&&sell[v][i]!=-1) res=max(res,sell[v][i]-buy[u][i]); return res; } void dijkstra(int S) { priority_queue<ii>s; dis[S][S]=0; s.push({0,S}); while(!s.empty()) { ii cc=s.top(); s.pop(); ll L=-cc.fs; int u=cc.sc; if(ktr[S][u]==1) continue; ktr[S][u]=1; for(auto v:g[u]) if(dis[S][v.sc]>L+v.fs) { dis[S][v.sc]=L+v.fs; s.push({-dis[S][v.sc],v.sc}); } } } ii dp[N]; bool check(int X) { for(int i=1;i<=n;i++) dp[i]={0,0}; for(int t=1;t<=n;t++) { for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) if(u!=v&&dis[u][v]<1e12) { dp[v]=max(dp[v],ii{dp[u].fs+max(0ll,cost[u][v])-dis[u][v]*X,dp[u].sc+1}); } } //cout<<cost[1][4]<<endl; // for(int i=1;i<=n;i++)cout<<dp[i].fs<<" "<<dp[i].sc<<endl; for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) if(u!=v&&dis[u][v]<1e12) { if(dp[v]<ii{dp[u].fs+max(0ll,cost[u][v])-dis[u][v]*X,dp[u].sc+1}) return 1; } return 0; } int32_t main() { #ifdef SKY freopen("A.inp","r",stdin); freopen("A.out","w",stdout); #endif // SKY ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) cin>>buy[i][j]>>sell[i][j]; for(int i=1;i<=m;i++) { int u,v,L; cin>>u>>v>>L; g[u].pb({L,v}); // g[v].pb({L,u}); } memset(cost,-0x3f3f,sizeof(cost)); memset(dis,0x3f3f,sizeof(dis)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cost[i][j]=get_cost(i,j); for(int i=1;i<=n;i++) dijkstra(i); // cout<<check(2)<<endl;return 0; int l=1,r=1e9,res=0; while(l<=r) { int mid=(l+r)/2; if(check(mid)) { res=mid; l=mid+1; }else r=mid-1; } cout<<res; 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...