Submission #198216

#	Time	Username	Problem	Language	Result	Execution time	Memory
198216		knon0501	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	164 ms	3704 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9+5;
int l[101][101];
int N,M,K;
int B[101][1001];
int S[101][1001];
int E[101][1001];
long long D[101][101];
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>N>>M>>K;

    int i,j,k;

    for(i=1 ; i<=N ; i++){
        for(j=1 ; j<=N; j++){
            l[i][j]=INF;
        }
        l[i][i]=0;
    }
    for(i=1 ; i<=N ; i++){
        for(j=1 ; j<=K ; j++){
            cin>>B[i][j]>>S[i][j];
        }
    }
    for(i=1 ; i<=M ; i++){
        int u,v,t;
        cin>>u>>v>>t;
        l[u][v]=t;
    }
    for(k=1 ; k<=N ; k++){
        for(i=1 ; i<=N ; i++){
            for(j=1 ; j<=N ; j++)
                l[i][j]=min(l[i][j],l[i][k]+l[k][j]);
        }
    }

    for(i=1 ; i<=N ; i++){
        for(j=1 ; j<=N ; j++){
            for(k=1 ; k<=K ; k++){
                if(S[j][k]>=0 && B[i][k]>=0)
                    E[i][j]=max(E[i][j],S[j][k]-B[i][k]);
            }
        }
    }
    int lef=0;
    int ans;
    int rig=INF;
    while(rig>=lef){
        long long mid=(lef+rig)/2;
        for(i=1 ; i<=N ; i++){
            for(j=1 ; j<=N ; j++){
                D[i][j]=mid*l[i][j]-E[i][j];
            }
            D[i][i]=INF;
        }
        for(k=1 ; k<=N ; k++)
            for(i=1 ; i<=N ; i++){
                for(j=1;  j<=N ; j++){
                    if(D[i][j]>D[i][k]+D[k][j])
                        D[i][j]=D[i][k]+D[k][j];
                }
            }
        int isok=0;
        for(i=1 ; i<=N ; i++){
            if(D[i][i]<=0)isok=1;
        }
        if(isok)lef=mid+1,ans=mid;
        else rig=mid-1;
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:74:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<ans;
     ~~~~^~~~~

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