Submission #119074

#	Time	Username	Problem	Language	Result	Execution time	Memory
119074		Charis02	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	175 ms	12260 KiB

merchant

#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 1004
#define INF 1e9+7

using namespace std;

ll n,m,k,u,v,t,ans;
ll buy[N][N];
ll sell[N][N];
ll dist[N][N],cost[N][N],test[N][N];

bool can(ll x)
{
    rep(i,0,n)
    {
        rep(j,0,n)
        {
            if(dist[i][j] != INF && x*dist[i][j] - cost[i][j] < INF)
                test[i][j] = cost[i][j] - x*dist[i][j];
            else
                test[i][j] = -INF;
        }
    }

    rep(p,0,n)
    {
        rep(i,0,n)
        {
            rep(j,0,n)
            {
                if(test[i][p] <= -INF || test[p][j] <= -INF)
                    continue;

                test[i][j] = max(test[i][j],test[i][p] + test[p][j]);

            }
        }
    }

    rep(i,0,n)
    {
        if(test[i][i] >= 0)
            return true;
    }

    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> k;

    rep(j,0,n)
    {
        rep(i,0,k)
        {
            cin >> buy[i][j] >> sell[i][j];
        }
    }

    rep(i,0,n)
    {
        rep(j,0,n)
        {
            dist[i][j] = INF;
        }
    }

    rep(i,0,m)
    {
        cin >> u >> v >> t;
        u--;
        v--;
        dist[u][v] = t;
    }

    rep(p,0,n)
    {
        rep(i,0,n)
        {
            rep(j,0,n)
            {
                dist[i][j] = min(dist[i][j],dist[i][p] + dist[p][j]);
            }
        }
    }

    rep(i,0,n)
    {
        rep(j,0,n)
        {
            if(dist[i][j] == INF)
                continue;

            rep(p,0,k)
            {
                if(buy[p][i] != -1 && sell[p][j] != -1)
                    cost[i][j] = max(cost[i][j],-buy[p][i] + sell[p][j]);
            }
        }

    }

    ll low = 0;
    ll high = 1000000001;
    ll ans = 0;

    while(low < high)
    {
        ll mid = (low + high) / 2;

        if(can(mid))
        {
            ans = max(ans,mid);
            low = mid+1;
        }
        else
        {
            high = mid-1;
        }
    }

    while(can(ans+1))
        ans++;

    cout << ans << endl;

    return 0;
}

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