제출 #402902

#제출 시각아이디문제언어결과실행 시간메모리
402902teehandsome여행하는 상인 (APIO17_merchant)C++11
0 / 100
23 ms1092 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define endl '\n' #define INF 1e9+7 #define all(x) x.begin(),x.end() using namespace std; using namespace __gnu_pbds; using ll=long long; using pii=pair<int,int>; using ppi=pair<int,pii>; using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>; template<typename T> void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";} void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";} template<typename T> void _print(T x) {cerr<<x;} void dbg() {cerr<<endl;} template<typename Head,typename... Tail> void dbg(Head H,Tail... T) { _print(H); if(sizeof...(T)) cerr<<","; else cerr<<"\"]"; dbg(T...); } #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define buy first #define sell second const int mxn=102; const int mxk=1010; int n,m,k; vector<pii> adj[mxn],adj2[mxn]; int dp[mxk]; pii shop[mxn][mxk]; int dist[mxn],dist2[mxn]; void dijk() { memset(dist,INF,sizeof(dist)); priority_queue<pii,vector<pii>,greater<pii>> pq; vector<bool> flag(n+1,false); dist[1]=0; pq.push({0,1}); while(!pq.empty()) { pii cur=pq.top(); pq.pop(); int d=cur.first,u=cur.second; flag[u]=true; for(auto vw:adj[u]) { int v=vw.first,w=vw.second; if(!flag[v] and d+w<dist[v]) { dist[v]=d+w; pq.push({dist[v],v}); } } } } void dijk2() { memset(dist2,INF,sizeof(dist2)); priority_queue<pii,vector<pii>,greater<pii>> pq; vector<bool> flag(n+1,false); pq.push({0,1}); dist2[1]=0; while(!pq.empty()) { pii cur=pq.top(); pq.pop(); int d=cur.first,u=cur.second; flag[u]=true; for(auto vw:adj2[u]) { int v=vw.first, w=vw.second; if(!flag[v] and d+w<dist2[v]) { dist2[v]=d+w; pq.push({dist2[v],v}); } } } } int main () { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>k; for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) { cin>>shop[i][j].buy>>shop[i][j].sell; } } for(int i=0;i<m;i++) { int u,v,w; cin>>u>>v>>w; adj[u].push_back({v,w}); adj2[v].push_back({u,w}); } dijk(); dijk2(); vector<int> dp_idx(k+1); int ans=0; for(int i=2;i<=n;i++) { for(int j=1;j<=k;j++) { if(shop[i][j].sell==-1 or shop[1][j].buy==-1) continue; int val=(shop[i][j].sell-shop[1][j].buy)/(dist2[i]+dist[i]); ans=max(ans,(shop[i][j].sell-shop[1][j].buy)/(dist2[i]+dist[i])); // debug(i,j,val); } } cout<<ans<<endl; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:104:17: warning: unused variable 'val' [-Wunused-variable]
  104 |             int val=(shop[i][j].sell-shop[1][j].buy)/(dist2[i]+dist[i]);
      |                 ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...