Submission #549876

#	Time	Username	Problem	Language	Result	Execution time	Memory
549876		FEDIKUS	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	123 ms	2396 KiB

merchant

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const ll maxn=110;
const ll maxk=1010;
 
ll n,m,k;
 
ll b[maxn][maxk];
ll s[maxn][maxk];
ll g[maxn][maxn];
ll newgt[maxn][maxn];
ll newgp[maxn][maxn];
ll checkg[maxn][maxn];
ll newcheckg[maxn][maxn];
 
void init(){
    for(auto &i:g) for(auto &j:i) j=-1;
    for(auto &i:newgt) for(auto &j:i) j=-1;
}
 
void floyd(ll g[maxn][maxn],ll res[maxn][maxn]){
    for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) res[i][j]=g[i][j];
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            for(ll k=0;k<n;k++){
                if(res[j][i]==-1) continue;
                if(res[i][k]==-1) continue;
                res[j][k]=min(res[j][k]==-1 ? INT_MAX:res[j][k],res[j][i]+res[i][k]);
            }
        }
    }
}
 
bool check(ll eff){
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            checkg[i][j]=-1;
            if(newgt[i][j]==-1) continue;
            checkg[i][j]=eff*newgt[i][j]-newgp[i][j];
        }
    }
    floyd(checkg,newcheckg);
    for(ll i=0;i<n;i++){
        if(newcheckg[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]>>s[i][j];
    }
    for(ll i=0;i<m;i++){
        ll v,w,t;
        cin>>v>>w>>t;
        v--,w--;
        g[v][w]=min(t,g[v][w]==-1 ? INT_MAX:g[v][w]);
    }
    floyd(g,newgt);
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            ll p=0;
            for(ll l=0;l<k;l++){
                if(s[j][l]==-1 || b[i][l]==-1) continue;
                p=max(p,s[j][l]-b[i][l]);
            }
            newgp[i][j]=p;
        }
    }
    /*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=0,r=INT_MAX,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