Submission #674912

#	Time	Username	Problem	Language	Result	Execution time	Memory
674912		Cookie	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	117 ms	4220 KiB

merchant

#include<bits/stdc++.h>

using namespace std;
#include<fstream>

#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#define pii pair<int, int>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll mod=  1e9 + 7;
const int mxk = 1e3, sq = 750, mxn = 105;
ll best[mxn + 1][mxn + 1], d[mxn + 1][mxn + 1], s[mxn + 1][mxk + 1], b[mxn + 1][mxk + 1], dis[mxn + 1][mxn + 1];
int n, m, k;
struct e{
    ll u, v, w;
};
vt<e>edge;
bool ck(ll mid){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dis[i][j] == 1e18)d[i][j] = 1e18;
            else d[i][j] = dis[i][j] * mid - best[i][j];
        }
    }
    
    for(int l = 1; l <= n; l++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(d[i][l] != 1e18 && d[l][j] != 1e18){
                    d[i][j] = min(d[i][j], d[i][l] + d[l][j]);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(d[i][i] <= 0)return(true);
    }
    return(false);
}
signed main(){
    ios_base::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];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)dis[i][j] = 1e18;
    }
    forr(i, 0, m){
        int u, v, w; cin >> u >> v >> w;
        
        dis[u][v] = w; 
    }   
    
    for(int l = 1; l <= n; l++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dis[i][j] = min(dis[i][j], dis[i][l] + dis[l][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            //if(i == j)continue;
            for(int l = 1; l <= k; l++){
                if(s[j][l] == -1 || b[i][l] == -1)continue;
                best[i][j] = max(best[i][j], s[j][l] - b[i][l]);
            }
        }
    }
    ll l = 1, r = 1e9, ans = 0;
    while(l <= r){
        ll mid = l + (r - l) / 2;
        if(ck(mid)){
            ans = mid; l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout << ans;
    return(0);
}

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