Submission #402902

#	Time	Username	Problem	Language	Result	Execution time	Memory
402902		teehandsome	Travelling Merchant (APIO17_merchant)	C++11	0 / 100	23 ms	1092 KiB

merchant

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

Compilation message (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]);
      |                 ^~~

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