Submission #249203

#	Time	Username	Problem	Language	Result	Execution time	Memory
249203		SamAnd	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	114 ms	3448 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 102, M = 9903, K = 1003;
const int INF = 1000000009;
const ll LINF = M * 1LL * INF;

int n, m, k;
int b[N][K], s[N][K];
ll sd[N][N];

int maxu[N][N];

ll d[N][N];
bool stg(int u)
{
    for (int x = 1; x <= n; ++x)
    {
        for (int y = 1; y <= n; ++y)
        {
            ll t;
            if (sd[x][y] > (long double)LINF / u)
                t = 2 * LINF;
            else
                t = sd[x][y] * u;
            d[x][y] = t - maxu[x][y];
            /*for (int i = 1; i <= k; ++i)
            {
                if (b[x][i] != -1 && s[y][i] != -1)
                    d[x][y] = min(d[x][y], t - (-b[x][i] + s[y][i]));
            }*/
        }
    }
    for (int z = 1; z <= n; ++z)
    {
        for (int x = 1; x <= n; ++x)
        {
            for (int y = 1; y <= n; ++y)
            {
                d[x][y] = min(d[x][y], d[x][z] + d[z][y]);
            }
        }
    }
    for (int x = 1; x <= n; ++x)
    {
        if (d[x][x] <= 0)
            return true;
    }
    return false;
}

void solv()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= k; ++j)
        {
            scanf("%d%d", &b[i][j], &s[i][j]);
        }
    }
    for (int x = 1; x <= n; ++x)
    {
        for (int y = 1; y <= n; ++y)
        {
            sd[x][y] = LINF;
        }
    }
    for (int i = 1; i <= m; ++i)
    {
        int x, y, d;
        scanf("%d%d%d", &x, &y, &d);
        sd[x][y] = min(sd[x][y], (ll)d);
    }

    for (int z = 1; z <= n; ++z)
    {
        for (int x = 1; x <= n; ++x)
        {
            for (int y = 1; y <= n; ++y)
            {
                sd[x][y] = min(sd[x][y], sd[x][z] + sd[z][y]);
            }
        }
    }

    for (int x = 1; x <= n; ++x)
    {
        for (int y = 1; y <= n; ++y)
        {
            maxu[x][y] = 0;
            for (int i = 1; i <= k; ++i)
            {
                if (b[x][i] != -1 && s[y][i] != -1)
                    maxu[x][y] = max(maxu[x][y], -b[x][i] + s[y][i]);
            }
        }
    }

    int l = 1, r = INF;
    int ans = 0;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (stg(m))
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    printf("%d\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

merchant.cpp: In function 'void solv()':
merchant.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &b[i][j], &s[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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