Submission #897833

#	Time	Username	Problem	Language	Result	Execution time	Memory
897833		Tenis0206	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	80 ms	2292 KiB

merchant

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 100;
const int kmax = 1000;
const int oo = INT_MAX;

int n,m,k;

int b[nmax + 5][kmax + 5], s[nmax + 5][kmax + 5];

int d[nmax + 5][nmax + 5], tr[nmax + 5][nmax + 5];

int rez[nmax + 5][nmax + 5];

bool ok(int cost)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(tr[i][j] != -oo)
            {
                rez[i][j] = tr[i][j] - d[i][j] * cost;
            }
            else
            {
                rez[i][j] = -oo;
            }
        }
    }
    for(int c=1; c<=n; c++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(rez[i][c] != -oo && rez[c][j] != -oo)
                {
                    rez[i][j] = max(rez[i][j], rez[i][c] + rez[c][j]);
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(rez[i][i] >= 0)
        {
            return true;
        }
    }
    return false;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=k; j++)
        {
            cin>>b[i][j]>>s[i][j];
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            d[i][j] = oo;
        }
    }
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        d[x][y] = min(d[x][y], c);
    }
    for(int c=1; c<=n; c++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(d[i][c] != oo && d[c][j] != oo)
                {
                    d[i][j] = min(d[i][j], d[i][c] + d[c][j]);
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            tr[i][j] = 0;
            for(int it=1; it<=k; it++)
            {
                if(b[i][it] == -1 || s[j][it] == -1 || d[i][j] == oo)
                {
                    continue;
                }
                tr[i][j] = max(tr[i][j], s[j][it] - b[i][it]);
            }
        }
    }
    int st = 0;
    int dr = 1e9;
    int rez = 0;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(ok(mij))
        {
            rez = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    cout<<rez<<'\n';
    return 0;
}

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