Submission #906422

#	Time	Username	Problem	Language	Result	Execution time	Memory
906422		dimashhh	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	71 ms	13536 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 1, MOD = 1e9 + 7;
typedef long long ll;
#define int ll
int n,k,m;
ll cost[N][N],d[N][N],G[N][N],b[N][N],s[N][N];
bool check(ll mid){
    for(int i =1 ;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(d[i][j] == 1e18){
                G[i][j] = d[i][j];
            }else{
                G[i][j] = -(cost[i][j] - mid * d[i][j]);
            }
        }
    }
    for(int t = 1;t <= n;t++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <=n;j++){
                G[i][j] = min(G[i][j],G[i][t] + G[t][j]);
            }
        }
    }
    for(int i = 1;i <= n;i++){
        if(G[i][i] <= 0) return true;
    }
    return false;
}
void test(){
    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 <= k;j++){
            for(int f = 1;f <= n;f++){
                if(b[i][j] != -1 && s[f][j] != -1){
                    cost[i][f] = max(cost[i][f],s[f][j] - b[i][j]);
                }
                d[i][f] = 1e18;
            }
        }
    }
    for(int i = 1;i <= m;i++){
        int x,y,w;
        cin >> x >> y >> w;
        d[x][y] = w;
    }
    
    for(int t = 1;t <= n;t++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <=n;j++){
                d[i][j] = min(d[i][j],d[i][t] + d[t][j]);
            }
        }
    }
    // return;
    ll l = 0,r = 1e9;
    while(r - l > 1){
        ll mid = (l + r) >> 1;
        if(check(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    cout << l;
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        test();
}

Compilation message (stderr)

merchant.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main()
      | ^~~~

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