Submission #643055

#	Time	Username	Problem	Language	Result	Execution time	Memory
643055		makanhulia	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	26 ms	1860 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 1e2+5, MOD = 1e9+7, M = 1e3+5;
ll tc = 1, n, m, ar[N], br[N], disre[N], dis[N];
ll x, y, k;
string s, s1, s2, ye = "YES", no = "NO";
vector<pairll> ed[N], rev[N];
bool by1 = 1;
ll buy[105][1005], sell[105][1005];

void input(){
  cin >> n >> m >> k;
  repp(i,1,n){
    repp(j,1,k){
      cin >> buy[i][j] >> sell[i][j];
      if (i > 1 && buy[i][j] != -1) by1 = 0;
    }
  }
  repp(i,1,m){
    ll x, y, w;
    cin >> x >> y >> w;
    ed[x].pb(mp(y,w));
    rev[y].pb(mp(x,w));
  }
}

void build(){
  repp(i,1,n) disre[i] = 1e18;
  disre[1] = 0;
  priority_queue<pairll, vector<pairll>, greater<pairll> > pq;
  pq.push(mp(0,1));
  while(pq.size()){
    pairll a = pq.top();
    pq.pop();
    for (auto i : rev[a.sc]){
      if (disre[i.fr] > disre[a.sc]+i.sc){
        disre[i.fr] = disre[a.sc]+i.sc;
        pq.push(mp(disre[i.fr],i.fr)); 
      }
    }
  }

  repp(i,1,n) dis[i] = 1e18;
  dis[1] = 0;
  pq.push(mp(0,1));
  while(pq.size()){
    pairll a = pq.top();
    pq.pop();
    for (auto i : ed[a.sc]){
      if (dis[i.fr] > dis[a.sc]+i.sc){
        dis[i.fr] = dis[a.sc]+i.sc;
        pq.push(mp(dis[i.fr],i.fr)); 
      }
    }
  }
}

void sub1(){
  build();
  ll ans = 0;
  repp(i,1,k){
    //for each item k find the most profitable route
    repp(idx,2,n){
      ll prof = sell[idx][i]-buy[1][i];
      ll tim = dis[idx]+disre[idx];
      ans = max(ans,prof/tim);
    }
  }
  cout << ans << "\n";
}

void sub2(){

}

void solve(){
  if (by1){
    sub1();
  }
  else{
    sub2();
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

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