Submission #780767

#	Time	Username	Problem	Language	Result	Execution time	Memory
780767		anton	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	232 ms	4320 KiB

merchant

#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;
}

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34