Submission #1160536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160536		jus_teng	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1096 ms	3496 KiB

merchant

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

/*SPFA algorithm adapted from https://cp-algorithms.com/graph/bellman_ford.html
Binary Search algorithm adapted from https://cp-algorithms.com/num_methods/binary_search.html
Modifications:
- Transformed state space where each node is (market, item state)
- Total number of states is n * (k + 1)
- k + 1 is item purchases
- vector<ld> dist(v, 0) set to 0
- queue<int> q starts with all nodes
- When item is bought at market, state transitions into (market, item owned)
- If an item is sold, (market, 0)
- Positive weight cycles instead of negative ones
- if (dist[u] + weight > dist[nextState] + eps) to maximize profit
- Binary search over lambda*/

typedef long long ll;
typedef double ld;

const ll maxN = 100;
const ll maxK = 1000;
const ld inf = 1e18;
const ld eps = 1e-12;

ll n, m, k;
vector<vector<pair<ll, ll>>> adj;
vector<vector<ll>> b, s;

bool SPFA(ld lambda){
    
    ll v = n * (k + 1);
    vector<ld> dist(v, 0);
    vector<int> visitCount(v, 0);
    vector<bool> inQueue(v, false);
    queue<int> q;

    for (ll i = 0; i < v; i++){
        
        q.push(i);
        inQueue[i] = true;
        visitCount[i] = 1;
    }

    while (!q.empty()){
        
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        ll currentMarket = u / (k + 1);
        ll itemState = u % (k + 1);

        if (itemState == 0){
            
            for (ll j = 0; j < k; j++){
                
                if (b[currentMarket][j] != -1){
                    
                    ll nextState = currentMarket * (k + 1) + (j + 1);
                    ld weight = -b[currentMarket][j] + eps;
                    
                    if (dist[u] + weight > dist[nextState] + eps){
                        
                        dist[nextState] = dist[u] + weight;
                        
                        if (!inQueue[nextState]){
                            
                            q.push(nextState);
                            inQueue[nextState] = true;
                            visitCount[nextState]++;
                            
                            if (visitCount[nextState] > v){
                                
                                return true;
                            }
                        }
                    }
                }
            }
            
        } 
        
        else{
            
            ll j = itemState - 1;
            if (s[currentMarket][j] != -1){
                
                ll nextState = currentMarket * (k + 1);
                
                ld weight = s[currentMarket][j] + eps;
                
                if (dist[u] + weight > dist[nextState] + eps){
                    
                    dist[nextState] = dist[u] + weight;
                    
                    if (!inQueue[nextState]){
                        
                        q.push(nextState);
                        inQueue[nextState] = true;
                        visitCount[nextState]++;
                        
                        if (visitCount[nextState] > v){
                            
                            return true;
                        }
                    }
                }
            }
        }

        for (auto p : adj[currentMarket]){
            
            ll nextMarket = p.first;
            ll travelTime = p.second;
            ll nextState = nextMarket * (k + 1) + itemState;
            ld weight = -lambda * travelTime + eps;
            
            if (dist[u] + weight > dist[nextState] + eps){
                
                dist[nextState] = dist[u] + weight;
                
                if (!inQueue[nextState]){
                    
                    q.push(nextState);
                    inQueue[nextState] = true;
                    visitCount[nextState]++;
                
                    if (visitCount[nextState] > v){
                        
                        return true;
                    }
                }
            }
        }
    }
    
    return false;
}

ll binSearch(){
    
    ld low = 0.0;
    ld high = 1e12;
    
    for (int iter = 0; iter < 100; iter++){
        
        ld mid = (low + high) / 2.0;
        
        if (SPFA(mid)){
            
            low = mid;
        } 
        
        else{
            
            high = mid;
        }
    }
    
    return (ll)floor(low);
}

int main(){
    
    scanf("%lld %lld %lld", &n, &m, &k);
    b.assign(n, vector<ll>(k));
    s.assign(n, vector<ll>(k));
    adj.resize(n);

    for (ll i = 0; i < n; i++){
        
        for (ll j = 0; j < k; j++){
            
            scanf("%lld %lld", &b[i][j], &s[i][j]);
        }
    }

    for (ll i = 0; i < m; i++){
        
        ll from, to, time;
        scanf("%lld %lld %lld", &from, &to, &time);
        adj[from - 1].emplace_back(to - 1, time);
    }

    printf("%lld\n", binSearch());
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     scanf("%lld %lld %lld", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:175:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |             scanf("%lld %lld", &b[i][j], &s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         scanf("%lld %lld %lld", &from, &to, &time);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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