Submission #444404

#	Time	Username	Problem	Language	Result	Execution time	Memory
444404		mjhmjh1104	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	114 ms	1328 KiB

merchant

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, k, b[106][1006], s[106][1006];
long long dist[106][106], c[106][106], cost[106][106];

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) scanf("%d%d", b[i] + j, s[i] + j);
    fill(dist[0], dist[105] + 106, (long long)1e9);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u--, v--;
        dist[u][v] = w;
    }
    for (int i = 0; i < 106; i++) dist[i][i] = 0;
    for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        int curr = 0;
        for (int l = 0; l < k; l++) if (b[i][l] != -1 && s[j][l] != -1) curr = max(curr, s[j][l] - b[i][l]);
        c[i][j] = curr;
    }
    int l = 0, r = 1e9 + 5;
    while (l < r) {
        int m = (l + r + 1) / 2;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (dist[i][j] == (long long)1e9) cost[i][j] = 4e18;
            else cost[i][j] = m * dist[i][j] - c[i][j];
        }
        for (int i = 0; i < n; i++) cost[i][i] = 4e18;
        for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cost[i][j] = min(cost[i][j], max(cost[i][k] + cost[k][j], (long long)-4e18));
        for (int i = 0; i < n; i++) if (cost[i][i] <= 0) {
            l = m;
            goto next;
        }
        r = m - 1;
        next:;
    }
    printf("%d", l);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:11:66: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) scanf("%d%d", b[i] + j, s[i] + j);
      |                                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d%d%d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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