Submission #657584

#	Time	Username	Problem	Language	Result	Execution time	Memory
657584		Alexandruabcde	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	27 ms	1484 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
constexpr int NMAX = 105;
constexpr int MMAX = 10002;
constexpr int KMAX = 1005;
constexpr LL INF = 1LL * 1e17;

struct Muchie {
    int x, y;
    LL cost;
};

Muchie Edge[MMAX];
int N, M, K;

LL B[NMAX][NMAX];
LL S[NMAX][NMAX];

LL profit[NMAX][NMAX];
LL timp[NMAX][NMAX];
bool can[NMAX][NMAX];

vector <PII> G[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    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 <= M; ++ i ) {
        cin >> Edge[i].x >> Edge[i].y >> Edge[i].cost;

        G[Edge[i].x].push_back({Edge[i].y, Edge[i].cost});
    }
}

void Reach (int Start) {
    queue <int> Q;
    Q.push(Start);
    for (int i = 1; i <= N; ++ i )
        timp[Start][i] = INF;
    timp[Start][Start] = 0;

    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        can[Start][nod] = true;

        for (auto it : G[nod]) {
            int to = it.first;

            if (timp[Start][to] > timp[Start][nod] + it.second) {
                timp[Start][to] = timp[Start][nod] + it.second;

                Q.push(to);
            }
        }
    }
}

void Precompute () {
    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 )
                profit[i][j] = max(profit[i][j], S[j][k] - B[i][k]);
        }
    }

    for (int i = 1; i <= N; ++ i )
        Reach(i);
}

LL ans[NMAX];
int Lg[NMAX];
bool use[NMAX];

LL TrueCost[NMAX][NMAX];

bool Good (LL cost) {
    for (int i = 1; i <= N; ++ i ) {
        for (int j = 1; j <= N; ++ j ) {
            if (i == j) continue;

            if (!can[i][j]) continue;

            TrueCost[i][j] = cost * timp[i][j] - profit[i][j];
        }
    }
    ///suma profit / suma timp >= cost
    ///suma profit - cost * suma timp >= 0
    ///cost * suma timp - suma profit <= 0

    ///Exista ciclu negativ ?
	
    for (int i = 1; i <= N; ++ i ) 
        ans[i] = INF;
    ans[1] = 0;
    Lg[1] = 1;
    queue <int> Q;
    Q.push(1);
    use[1] = true;

    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        use[nod] = false;

        for (int i = 1; i <= N; ++ i ) {
            if (!can[nod][i]) continue;

            if (ans[i] > ans[nod] + TrueCost[nod][i]) {
                ans[i] = ans[nod] + TrueCost[nod][i];
                Lg[i] = Lg[nod] + 1;

                if (Lg[i] > N) {
                    return true;
                }

                if (!use[i]) {
                    use[i] = true;
                    Q.push(i);
                }
            }
        }
    }

    return false;
}

void Solve () {
    LL st = 1, dr = 1000000000;
    LL ans = 0;

    while (st <= dr) {
        LL mij = (st + dr) / 2;

        if (Good(mij)) {
            st = mij + 1;
            ans = mij;
        }
        else dr = mij - 1;
    }

    cout << ans << '\n';
}

int main () {
    Read();
    Precompute();
    Solve();

    return 0;
}

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