Submission #919390

#	Time	Username	Problem	Language	Result	Execution time	Memory
919390		vnm06	Travelling Merchant (APIO17_merchant)	C++14	33 / 100	111 ms	2364 KiB

merchant

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

using namespace std;

long long inf=4e18;
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 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;
            }
        }

    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]==inf || distc[k][j]==inf) continue;
                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]==inf || distc[k][j]==inf) continue;
                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;
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) vreme[i][j]=inf;
        vreme[i][i]=0;
    }
    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];
        }
    }
    long long le=0, ri=1e9+1;
    while(ri-le>1)
    {
        long long mid=(le+ri)/2;
        if(pos(mid)) le=mid;
        else ri=mid;
    }
    cout<<le<<endl;
    return 0;
}

/**
4 5 2
10 9 5 -1
6 4 20 -1
9 7 10 -1
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

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