Submission #549859

#	Time	Username	Problem	Language	Result	Execution time	Memory
549859		FEDIKUS	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	109 ms	2128 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn=110;
const ll maxk=1010;
const ll inf=LLONG_MAX;

ll n,m,k;

ll b[maxn][maxk];
ll s[maxn][maxk];
ll gt[maxn][maxn];
ll gp[maxn][maxn];
ll checkg[maxn][maxn];

void init(){
    for(auto &i:gt) for(auto &j:i) j=inf;
}

void floyd(ll g[maxn][maxn]){
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            for(ll l=0;l<n;l++){
                if(g[j][i]==inf) continue;
                if(g[i][l]==inf) continue;
                g[j][l]=min(g[j][l],g[j][i]+g[i][l]);
            }
        }
    }
}

bool check(ll eff){
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            checkg[i][j]=inf;
            if(gt[i][j]==inf) continue;
            checkg[i][j]=eff*gt[i][j]-gp[i][j];
        }
    }
    floyd(checkg);
    for(ll i=0;i<n;i++){
        if(checkg[i][i]<=0) return true;
    }
    return false;
}

int main(){
    cin>>n>>m>>k;
    init();
    for(ll i=0;i<n;i++){
        for(ll j=0;j<k;j++) cin>>b[i][j];
        for(ll j=0;j<k;j++) cin>>s[i][j];
    }
    for(ll i=0;i<m;i++){
        ll v,w,t;
        cin>>v>>w>>t;
        v--,w--;
        gt[v][w]=min(t,gt[v][w]);
    }
    floyd(gt);
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            gp[i][j]=0;
            for(ll l=0;l<k;l++){
                if(s[j][l]==-1 || b[i][l]==-1) continue;
                gp[i][j]=max(gp[i][j],s[j][l]-b[i][l]);
            }
        }
    }
    /*for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            cout<<newgt[i][j]<<" ";
        }
        cout<<"\n";
    }cout<<"\n";
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            cout<<newgp[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    ll l=1,r=1e9,res=-1;
    while(l<=r){
        ll mid=l+(r-l)/2;
        if(check(mid)){
            res=mid;
            l=mid+1;
        }else r=mid-1;
    }
    cout<<res;
    return 0;
}

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