Submission #232022

#	Time	Username	Problem	Language	Result	Execution time	Memory
232022		parsa_mobed	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	88 ms	3832 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair <int , int>
#define F first
#define S second
const int N = 101, K = 1001, inf = 1e16;
int cost[N][N], dis[N][N], B[N][K], S[N][K];
pii ans[N];

bool Less(int i, int j, int k) {
    int D = dis[i][k] + dis[k][j], C = cost[i][k] + cost[k][j];
    return cost[i][j] * D < C * dis[i][j];
}
void Max(pii &A, pii B) {if (B.F * A.S > A.F * B.S) A = B;}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m, k; 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 u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++)
            for (int i = 1; i <= k; i++) if (B[u][i] != -1 && S[v][i] != -1)
                cost[u][v] = max(cost[u][v], S[v][i] - B[u][i]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = inf;
    for (int i = 0; i < m; i++) {int u, v, w; cin >> u >> v >> w, dis[u][v] = w;}
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    /*for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) if (dis[i][j] < inf && Less(i, j, k))
                cost[i][j] = cost[i][k] + cost[k][j], dis[i][j] = dis[i][k] + dis[k][j];
    if (dis[1][1] >= inf) return cout << "0\n", 0;
    cout << cost[1][1] << " " << dis[1][1] << "\n";
    cout << cost[1][1] / dis[1][1] << "\n";*/
    for (int i = 1; i <= n; i++) ans[i] = {cost[1][i], dis[1][i]};
    for (int i = 1; i <= K; i++)
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++) if (u != v) Max(ans[v], {ans[u].F + cost[u][v], ans[u].S + dis[u][v]});
    if (ans[1].S == 0) return cout << "0\n", 0;
    cout << ans[1].F / ans[1].S << "\n";

    return 0;
}

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