Submission #316160

#	Time	Username	Problem	Language	Result	Execution time	Memory
316160		phathnv	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	113 ms	1400 KiB

merchant

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Merchant"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 101;
const int K = 1001;
const int INF = 1e9;
const ll LLINF = 1e18;

int n, m, k, s[N][K], b[N][K], a[N][N], best[N][N];

ll cost[N][N];

void readInput(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= k; j++)
            cin >> b[i][j] >> s[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if (i != j)
                a[i][j] = -1;
    for(int i = 1; i <= m; i++){
        int u, v, t;
        cin >> u >> v >> t;
        if (a[u][v] == -1)
            a[u][v] = t;
        else
            a[u][v] = min(a[u][v], t);
    }
}

void prepare(){
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (a[i][k] != -1 && a[k][j] != -1 && (a[i][j] == -1 || a[i][j] > a[i][k] + a[k][j]))
                    a[i][j] = a[i][k] + a[k][j];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int c = 1; c <= k; c++)
                if (s[j][c] != -1 && b[i][c] != -1)
                    best[i][j] = max(best[i][j], s[j][c] - b[i][c]);
}

bool check(int x){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            if (i == j)
                cost[i][j] = LLINF;
            else
                cost[i][j] = (ll) x * a[i][j] - best[i][j];
        }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (a[i][k] != -1 && a[k][j] != -1)
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
    for(int i = 1; i <= n; i++)
        if (cost[i][i] <= 0)
            return 1;
    return 0;
}

void solve(){
    int l = 0, r = INF, res = 0;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (check(mid)){
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << res;
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    prepare();
    solve();
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   92 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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