Submission #672459

#	Time	Username	Problem	Language	Result	Execution time	Memory
672459		danikoynov	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	178 ms	5384 KiB

merchant

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 1100, maxk = 1010;
const ll inf = 1e17;

int n, m, k;
ll dist[maxn][maxn], b[maxn][maxk], s[maxn][maxk];
ll profit[maxn][maxn], dp[maxn][maxn];

void floyd_warshall()
{
    for (int p = 1; p <= n; p ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
            {
                if (dist[i][p] + dist[p][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][p] + dist[p][j];
                }
            }
}


void bin_floyd()
{
    for (int p = 1; p <= n; p ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
            {
                if (dp[i][p] + dp[p][j] < dp[i][j])
                {
                    dp[i][j] = dp[i][p] + dp[p][j];
                }
            }
}

void build_graph(ll mf)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j ++)
        {

        if (mf == 0)
            dp[i][j] = -profit[i][j];
        else
            dp[i][j] = mf * min(dist[i][j], inf / mf) - profit[i][j];
            ///cout << i << " " << j << " " << dp[i][j] << " : " << dist[i][j] << " : " << profit[i][j] << endl;
        }
}


bool check(ll mf)
{
    build_graph(mf);
    bin_floyd();
    bool neg = false;
    for (int i = 1; i <= n; i ++)
        if (dp[i][i] <= 0)
            neg = true;
    return neg;
}

void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            dist[i][j] = inf;
        for (int j = 1; j <= k; j ++)
            cin >> b[i][j] >> s[i][j];
    }

    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        ll w;
        cin >> v >> u >> w;
        dist[v][u] = min(dist[v][u], w);
    }

    floyd_warshall();


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


    ll lf = 0, rf = 1e9;
    while(lf <= rf)
    {
        ll mf = (lf + rf) / 2;
        if (check(mf))
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    cout << max((ll)0, rf) << endl;


}

int main()
{
    solve();
    return 0;
}

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