Submission #369418

#	Time	Username	Problem	Language	Result	Execution time	Memory
369418		Vladth11	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	154 ms	1516 KiB

merchant

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
//#include "shoes.h"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 101;
const ll INF = (1LL << 30);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 35;
const double eps = 0.000000001;

double d[NMAX];

struct Edges {
    int a, b;
    double c;
};

vector <Edges> v;
int dist[NMAX][NMAX];
int profit[NMAX][NMAX];
int n, m, k;
int b[NMAX][1001], s[NMAX][1001];

bool OK(double r) {
    v.clear();
    for(int i = 1; i <= n; i++) {
        d[i] = 1e9;
        for(int j = 1; j <= n; j++) {
            if(i == j)
                continue;

            v.push_back({i, j, r * dist[i][j] - profit[i][j]});
        }
    }
    d[1] = 0;
    int ok = 1;
    for(int i = 1; i < n; i++) {
        ok = 0;
        for(auto x : v) {
            if(d[x.a] + x.c < d[x.b]){
                d[x.b] = d[x.a] + x.c;
                ok = 1;
            }
        }
    }
    return ok;
}

int main() {
    int i;
    cin >> n >> m >> k;
    for(i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            cin >> b[i][j] >> s[i][j];
        }
    }
    for(i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int maxim = 0;
            dist[i][j] = 1e9;
            for(int t = 1; t <= k; t++) {
                if(s[j][t] != -1 && b[i][t] != -1)
                maxim = max(maxim, s[j][t] - b[i][t]);
            }
            profit[i][j] = maxim;
        }
    }
    for(i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = c;
    }
    for(int t = 1; t <= n; t++) {
        for(i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);
            }
        }
    }
    double r = 0, pas = (1 << 20);
    while(pas > eps){
        if(OK(r + pas))
        r += pas;
        pas /= 2;
    }
    r += eps;
    cout << r;
    return 0;
}

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