Submission #792352

#	Time	Username	Problem	Language	Result	Execution time	Memory
792352		Alish	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	90 ms	724 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define int             ll

const int N = 123;
const ll INF=1e15;
const int M=1e9+23;
ll dist[N][N];
ll prof[N][N];
ll b[N][N], s[N][N];
ll temp[N][N];

int n , m, k ;


bool check(int x){
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++){
            temp[i][j]=+ prof[i][j]-x*dist[i][j];
        }
        if(prof[i][i]==0 && temp[i][i]==0)temp[i][i]=-1;
    }

    for (int kk=1; kk<=n; kk++){
        for(int i=1; i<=n; i++){
            for (int j=1; j<=n; j++){
                temp[i][j]= max(temp[i][j], temp[i][kk]+ temp[kk][j]);
            }
        }
    }
    for (int i=1; i<=n; i++) if(temp[i][i]>=0) return 1;
    return 0;
}



int32_t main()
{
    cin>>n>>m>>k;

    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++) dist[i][j]=INF;
        for (int j=1; j<=k; j++) cin>>b[i][j]>>s[i][j];
    }
    for (int i=1; i<=n; i++) dist[i][i]=0;
    for (int i=0; i<m; i++){
        ll v, u, w; cin>>v>>u>>w;
        dist[v][u]=min(dist[v][u], w);
    }

    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            for (int kk=1; kk<=k; kk++){
                if(b[i][kk]!=-1 && s[j][kk]!=-1)prof[i][j]=max(prof[i][j], s[j][kk]-b[i][kk]);
            }
        }
    }
    for (int kk=1; kk<=n; kk++){
        for (int i=1; i<=n; i++){
            for (int j=1; j<=n; j++){
                dist[i][j]=min(dist[i][j], dist[i][kk]+ dist[kk][j]);
            }
        }
    }

    int l=0,  r= 1e9+1;
    while(r-l>1) {

        int mid=(r+l)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<l<<endl;

}

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