Submission #106440

#	Time	Username	Problem	Language	Result	Execution time	Memory
106440		Kastanda	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	474 ms	3400 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 109, K = 1009;
int n, m, k, B[N][K], S[N][K];
ll D[N][N], dp[N][N];
inline bool Solve(ll md)
{
    memset(dp, -63, sizeof(dp));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && D[i][j] <= INT_MAX)
            {
                dp[i][j] = 0;
                for (int h = 1; h <= k; h++)
                    if (B[i][h] != -1 && S[j][h] != -1)
                        dp[i][j] = max(dp[i][j], (ll)S[j][h] - B[i][h]);
                dp[i][j] -= md * D[i][j];
            }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]);
    for (int i = 1; i <= n; i++)
        if (dp[i][i] >= 0)
            return 1;
    return 0;
}
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]);
    memset(D, 63, sizeof(D));
    for (int i = 1, v, u; i <= m; i++)
        scanf("%d%d", &v, &u), scanf("%lld", &D[v][u]);
    for (int i = 1; i <= n; i++)
        D[i][i] = 0;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
    ll le = 0, ri = 1873428744, md;
    while (ri - le > 1)
    {
        md = (le + ri) >> 1;
        if (Solve(md))
            le = md;
        else
            ri = md;
    }
    return !printf("%lld\n", le);
}

Compilation message (stderr)

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

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