Submission #919369

#	Time	Username	Problem	Language	Result	Execution time	Memory
919369		vnm06	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	110 ms	4120 KiB

merchant

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

using namespace std;

long long inf=2e18;
long long n, m, k;
long long b[105][1005], s[105][1005];
long long vreme[105][105];
long long val[105][105];
long long ed[105][105];
long long distc[105][105];

bool pos(long long x)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(vreme[i][j]!=inf) ed[i][j]=x*vreme[i][j]-val[i][j];
            else ed[i][j]=inf;
            distc[i][j]=ed[i][j];
        }
    }
    for(int i=1; i<=n; i++) distc[i][i]=0;

    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(distc[i][k]+distc[k][j]<distc[i][j]) distc[i][j]=distc[i][k]+distc[k][j];
            }
        }
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(distc[i][k]+distc[k][j]<distc[i][j]) return 1;
            }
        }
    }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(i==j) continue;
                if(distc[i][j]+distc[j][i]==0) return 1;
            }
        }
    return 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.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];
            if(b[i][j]==-1) b[i][j]=inf;
            if(s[i][j]==-1) s[i][j]=-1;
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) vreme[i][j]=inf;
    }
    for(int i=0; i<m; i++)
    {
        int u, v, d;
        cin>>u>>v>>d;
        vreme[u][v]=d;
    }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(vreme[i][k]+vreme[k][j]<vreme[i][j]) vreme[i][j]=vreme[i][k]+vreme[k][j];
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int t=1; t<=k; t++) if(val[i][j]<s[j][t]-b[i][t]) val[i][j]=s[j][t]-b[i][t];
        }
    }
    int le=0, ri=1e9;
    while(ri-le>1)
    {
        int mid=(le+ri)/2;
        if(pos(mid)) le=mid;
        else ri=mid;
    }
    cout<<le<<endl;
    return 0;
}

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