Submission #1198348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198348		ivaziva	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	65 ms	2112 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

#define MAXN 101
#define MAXM 1001
#define int long long

int n,m,k;
int buy[MAXN][MAXM],sell[MAXN][MAXM];
int adj[2][MAXN][MAXN],profit[MAXN][MAXN];

bool check(int mid)
{
    for (int node1=1;node1<=n;node1++)
    {
        for (int node2=1;node2<=n;node2++) adj[1][node1][node2]=mid*min(adj[0][node1][node2],LLONG_MAX/mid)-profit[node1][node2];
    }
    for (int node=1;node<=n;node++)
    {
        for (int node1=1;node1<=n;node1++)
        {
            for (int node2=1;node2<=n;node2++)
            {
                if (adj[1][node1][node]==LLONG_MAX or adj[1][node][node2]==LLONG_MAX) continue;
                adj[1][node1][node2]=min(adj[1][node1][node2],adj[1][node1][node]+adj[1][node][node2]);
            }
        }
    }
    for (int node=0;node<=n;node++)
    {
        if (adj[1][node][node]<0) return false;
    }
    return true;
}

int32_t main()
{
    cin>>n>>m>>k;
    for (int node=1;node<=n;node++)
    {
        for (int item=1;item<=k;item++) cin>>buy[node][item]>>sell[node][item];
        for (int sled=1;sled<=n;sled++) adj[0][node][sled]=LLONG_MAX;
    }
    for (int i=1;i<=m;i++) {int node1,node2,time;cin>>node1>>node2>>time;adj[0][node1][node2]=time;}
    for (int node=1;node<=n;node++)
    {
        for (int node1=1;node1<=n;node1++)
        {
            for (int node2=1;node2<=n;node2++)
            {
                if (adj[0][node1][node]==LLONG_MAX or adj[0][node][node2]==LLONG_MAX) continue;
                adj[0][node1][node2]=min(adj[0][node1][node2],adj[0][node1][node]+adj[0][node][node2]);
            }
        }
    }
    for (int node1=1;node1<=n;node1++)
    {
        for (int node2=1;node2<=n;node2++)
        {
            for (int item=1;item<=k;item++)
            {
                if (buy[node1][item]==-1 or sell[node2][item]==-1) continue;
                profit[node1][node2]=max(profit[node1][node2],sell[node2][item]-buy[node1][item]);
            }
        }
    }
    int l=1,r=INT_MAX,rez=0;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (check(mid)) {rez=mid;r=mid-1;}
        else l=mid+1;
    }
    cout<<rez<<endl;
}

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