Submission #210713

#	Time	Username	Problem	Language	Result	Execution time	Memory
210713		anonymous	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	121 ms	3452 KiB

merchant

#include<iostream>
#define MAXN 105
#define MAXK 1005
#define LL long long
using namespace std;
int N, M, K, ui, vi, wi;
int buy[MAXN][MAXK], sell[MAXN][MAXK];
LL dist[MAXN][MAXN], best[MAXN][MAXN];
LL adj[MAXN][MAXN];
bool can(LL k) {
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            adj[i][j] = best[i][j] - k*dist[i][j];
        }
    } //is there a non-negative cycle?
    for (int m=1; m<=N; m++) {
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                adj[i][j]=max(adj[i][j], adj[i][m] + adj[m][j]);
            }
        }
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            if (i != j && adj[i][j] + best[j][i] - k*dist[j][i] >= 0) {return(true);}
        }
    }
    return(false);
}
int main() {
    //freopen("merchin.txt","r",stdin);
    scanf("%d %d %d",&N,&M,&K);
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=K; j++) {
            scanf("%d %d", &buy[i][j], &sell[i][j]);
        }
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            if (i != j) {dist[i][j] = 1LL << 31;}
        }
    }
    for (int i=0; i<M; i++) {
        scanf("%d %d %d",&ui,&vi,&wi);
        dist[ui][vi]=wi;
    }
    for (int k=1; k<=N; k++) {
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                dist[i][j]=min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            for (int k=1; k<=K; k++) {
                if (sell[j][k] == -1 || buy[i][k] == -1) {continue;}
                best[i][j] = max(best[i][j], (LL) sell[j][k]-buy[i][k]);
            }
        }
    }
    int lo = 0, hi = (int) 1e9 + 5;
    while (lo + 1 != hi) {
        int mid = (lo + hi) >> 1;
        if (can(mid)) {lo = mid;}
        else {hi = mid;}
    }
    printf("%d\n", lo);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&N,&M,&K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
merchant.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &buy[i][j], &sell[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&ui,&vi,&wi);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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