Submission #316152

#	Time	Username	Problem	Language	Result	Execution time	Memory
316152		phathnv	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	181 ms	3328 KiB

merchant

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Merchant"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 101;
const int K = 1001;
const int INF = 1e9;
const ll LLINF = 1e18;

int n, m, k, s[N][K], b[N][K], a[N][N], best[N][N];

int vst[N], Time;
bool inQueue[N], done[N];
vector <int> trace[N];
ll dist[N], cost[N][N];

void readInput(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    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++)
            if (i != j)
                a[i][j] = -1;
    for(int i = 1; i <= m; i++){
        int u, v, t;
        cin >> u >> v >> t;
        if (a[u][v] == -1)
            a[u][v] = t;
        else
            a[u][v] = min(a[u][v], t);
    }
}

void prepare(){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int c = 1; c <= k; c++)
                if (s[j][c] != -1 && b[i][c] != -1)
                    best[i][j] = max(best[i][j], s[j][c] - b[i][c]);
}

void floydWarshall(){
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (a[i][k] != -1 && a[k][j] != -1 && (a[i][j] == -1 || a[i][j] > a[i][k] + a[k][j]))
                    a[i][j] = a[i][k] + a[k][j];
}

void dfs(int u){
    if (vst[u] == Time)
        return;
    vst[u] = Time;
    for(int v : trace[u])
        dfs(v);
}

bool check(int x){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cost[i][j] = (ll) x * a[i][j] - best[i][j];

    for(int i = 1; i <= n; i++)
        done[i] = 0;

    for(int s = 1; s <= n; s++){
        if (done[s])
            continue;

        for(int i = 1; i <= n; i++){
            dist[i] = LLINF;
            trace[i].clear();
            inQueue[i] = 0;
        }

        queue <int> qu;
        dist[s] = 0;
        qu.push(s);
        inQueue[s] = 1;
        while (!qu.empty()){
            int u = qu.front();
            qu.pop();
            inQueue[u] = 0;

            for(int v = 1; v <= n; v++){
                if (v == u)
                    continue;

                if (dist[v] >= dist[u] + cost[u][v] && a[u][v] != -1 && !done[v]){
                    ++Time;
                    dfs(u);
                    if (vst[v] == Time)
                        return 1;
                }

                if (dist[v] > dist[u] + cost[u][v] && a[u][v] != -1 && !done[v]){
                    dist[v] = dist[u] + cost[u][v];
                    trace[v].clear();
                    trace[v].push_back(u);
                    if (!inQueue[v]){
                        qu.push(v);
                        inQueue[v] = 1;
                    }
                } else if (dist[v] == dist[u] + cost[u][v] && a[u][v] != -1 && !done[v]){
                    trace[v].push_back(u);
                }
            }
        }
        for(int i = 1; i <= n; i++)
            if (dist[i] != LLINF)
                done[i] = 1;
    }
    return 0;
}

void solve(){
    int l = 0, r = INF, res = 0;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (check(mid)){
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << res;
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    prepare();
    floydWarshall();
    solve();
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  143 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  144 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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