Submission #953193

#	Time	Username	Problem	Language	Result	Execution time	Memory
953193		Itamar	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	162 ms	4296 KiB

merchant

#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>

const int siz = 101;
const int MK = 1001;
ll dis[siz][siz];
ll pro[siz][siz];
ll pr[siz][2*MK];
int main()
{
    int n, m, K;
    cin >> n >> m >> K;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j)dis[i][j] = 1e9;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2 * K; j++) {
            cin >> pr[i][j];
            if (pr[i][j] == -1) {
                if (j % 2)pr[i][j] = -1e18;
                else pr[i][j] = 1e18;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        dis[a][b] = min(dis[a][b],c);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 2*K; k+=2) {
                pro[i][j] = max(pro[i][j], -pr[i][k] + pr[j][k + 1]);
            }
        }
    }
    int l = 0, r=1e9;
    while (l < r) {
        int mid = (l + r+1) / 2;
        // is it possible that profit/dis >= mid  <--> mid*dis - profit <= 0?
        vector<vll> procur(n, vll(n,1e18));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    procur[i][j] = min(procur[i][j], mid * (dis[i][k] + dis[k][j]) - pro[k][j]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i!=j)procur[i][j] = 200 * procur[i][j] - 1;
            }
        }
        vll dp(n,1e18);
        dp[0] = 0;
        bool f = 0;
        for (int it = 0; it <= n; it++) {
            vll dpt= dp;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (it == n && dpt[i] > dp[j] + procur[j][i])f = 1;
                    dpt[i] = min(dpt[i], dp[j] + procur[j][i]);
                }
            }
            dp = dpt;
        }
        if (f == 1) {
            l = mid;
        }
        else {
            r = mid-1;
        }
    }
    cout << l;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

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