제출 #780767

#제출 시각아이디문제언어결과실행 시간메모리
780767anton여행하는 상인 (APIO17_merchant)C++17
100 / 100
232 ms4320 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int INF = (1LL<<61LL)-1LL; int n, m, k; struct Price{ int buy, sell; Price(){ } Price(int a, int b){ buy = a; sell = b; } }; vector<vector<Price>> prices; struct Road{ int dest, time; Road(int a, int b){ dest = a; time = b; } }; vector<vector<Road>>adj; vector<vector<int>> best_t; vector<vector<int>> best_p; struct Node{ int id, prio; Node(int a, int b){ id = a; prio = b; } }; void bfs(int source){ vector<int> vis(n, INF); vis[source] = 0; auto cmp = [&](Node a, Node b){ return a.prio<b.prio; }; priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp); pq.push(Node(source, 0)); while(pq.size()>0){ auto cur = pq.top(); pq.pop(); if(vis[cur.id] >= cur.prio){ for(auto next: adj[cur.id]){ Node ev = Node(next.dest, cur.prio + next.time); if(ev.prio<vis[next.dest]){ pq.push(ev); vis[next.dest] = ev.prio; } } } } for(int i = 0; i<n; i++){ best_t[source][i] = vis[i]; } } bool pos_loop(int rate){ auto cmp = [&](pii a, pii b){ if(a.first!=b.first){ return a.first>b.first; } return a.second>b.second; }; vector<pii> best_s(n,pii(0, 0)); bool improve = true; for(int step = 0; step<2*n+42; step++){ improve = false; for(int i = 0; i<n; i++){ for(int j = 0; j<n; j++){ if(i!=j && best_t[i][j]!=INF){ pii c = pii(best_s[i].first + best_p[i][j] - rate *best_t[i][j], best_s[i].second+1); if(cmp(c,best_s[j])){ improve = true; best_s[j]= c; } } } } } if(improve){ return true; } return false; } signed main(){ cin>>n>>m>>k; prices.resize(n, vector<Price> (k)); for(int i = 0; i<n; i++){ for(int e = 0; e<k; e++){ cin>>prices[i][e].buy>>prices[i][e].sell; if(prices[i][e].buy==-1){ prices[i][e].buy = INF; } if(prices[i][e].sell==-1){ prices[i][e].sell=-INF; } } } adj.resize(n); best_t.resize(n, vector<int> (n)); for(int i =0; i<m; i++){ int a, b, t; cin>>a>>b>>t; a--;b--; adj[a].push_back(Road(b, t)); //cout<<"road "<<a<<" "<<b<<" "<<t<<endl; } for(int i = 0; i<n; i++){ bfs(i); } //cout<<"best_t"<<endl; for(int i =0; i<n; i++){ for(int j = 0; j<n; j++){ //cout<<best_t[i][j]<<" "; } //cout<<endl; } best_p.resize(n, vector<int> (n, 0)); for(int i= 0; i<n; i++){ for(int j = 0; j<n; j++){ for(int p = 0; p<k; p++){ best_p[i][j] = max(best_p[i][j], prices[j][p].sell - prices[i][p].buy); } } } int res= 0; for(int step = (1LL<<30LL); step>=1; step/=2){ if(pos_loop(res+step)){ res+=step; } } cout<<res<<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...