Submission #107406

#	Time	Username	Problem	Language	Result	Execution time	Memory
107406		kuroni	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	126 ms	1500 KiB

merchant

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 105, K = 1005;
const long long INF = 4E18 + 7;

int n, m, k, u, v, w[N][N], b[N][K], s[N][K];
long long dis[N][N], tmp[N][N];

bool floyd(long long dis[N][N])
{
    for (int mi = 1; mi <= n; mi++)
        for (int le = 1; le <= n; le++)
            for (int ri = 1; ri <= n; ri++)
                dis[le][ri] = min(dis[le][ri], max(-INF, dis[le][mi] + dis[mi][ri]));
    for (int st = 1; st <= n; st++)
        for (int mi = st + 1; mi <= n; mi++)
            if (dis[st][mi] + dis[mi][st] <= 0)
                return true;
    return false;
}

int main()
{
    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 j = 1; j <= n; j++)
            if (j != i)
                dis[i][j] = INF;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int t = 1; t <= k; t++)
                if (b[i][t] != -1 && s[j][t] != -1)
                    w[i][j] = max(w[i][j], s[j][t] - b[i][t]);
    while (m--)
    {
        scanf("%d%d", &u, &v);
        scanf("%lld", &dis[u][v]);
    }
    floyd(dis);
    int le = 1, ri = 1E9;
    while (le <= ri)
    {
        int mi = (le + ri) / 2;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dis[i][j] == INF)
                    tmp[i][j] = INF;
                else
                    tmp[i][j] = dis[i][j] * mi - w[i][j];
        if (floyd(tmp))
            le = mi + 1;
        else
            ri = mi - 1;
    }
    printf("%d", ri);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:26: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:30: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:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~
merchant.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &dis[u][v]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

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