Submission #989060

#	Time	Username	Problem	Language	Result	Execution time	Memory
989060		Tsagana	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	52 ms	4316 KiB

merchant

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define alnl(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int N, M, K;
lnl B[105][1005];
lnl S[105][1005];
lnl mat[105][105];
lnl mindis[105][105];
lnl profit[105][105];
 
bool check(lnl x) {
    for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
        if (mindis[i][j] == 1e13 || i == j) mat[i][j] = -1e13;
        else mat[i][j] = profit[i][j] - (x * mindis[i][j]);
    }
    for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
        mat[i][j] = max(mat[i][j], mat[i][k] + mat[k][j]);
    }
    for (int i = 1; i <= N; i++) {
        if (mat[i][i] >= 0) return 1;
    }
    return 0;
}
void solve () {
	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++)
    	mindis[i][j] = 1e13;
        mindis[i][i] = 0;
    }
    while (M--) {
        int u, v; lnl w;
        cin >> u >> v >> w;
        mindis[u][v] = w;
    }
    for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
        mindis[i][j] = min(mindis[i][j], mindis[i][k] + mindis[k][j]);
    }
    for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
        if (i == j) continue;
        profit[i][j] = 0;
        for (int k = 1; k <= K; k++) {
            if (B[i][k] == -1 || S[j][k] == -1) continue;
            profit[i][j] = max(profit[i][j], S[j][k] - B[i][k]);
        }
    }
    lnl l = 0, r = 1e9;
    while (l < r) {
        lnl m = (l + r + 1) / 2;
        if (check(m)) l = m;
        else r = m - 1;
    }
    cout << l;
}
int main() {IOS solve(); return 0;}

Compilation message (stderr)

merchant.cpp: In function 'void solve()':
merchant.cpp:48:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   48 |     for (int j = 1; j <= N; j++)
      |     ^~~
merchant.cpp:50:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   50 |         mindis[i][i] = 0;
      |         ^~~~~~

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