제출 #734749

#제출 시각아이디문제언어결과실행 시간메모리
734749bin9638여행하는 상인 (APIO17_merchant)C++17
0 / 100
9 ms16396 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+cost[u][v]-dis[u][v]*X,dp[u].sc+1}); } } 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+cost[u][v]-dis[u][v]*X,dp[u].sc+1}) return 1; } return 0; } int32_t main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); 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); 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; }

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp: In function 'int32_t main()':
merchant.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     freopen("A.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("A.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...