Submission #316148

#	Time	Username	Problem	Language	Result	Execution time	Memory
316148		phathnv	여행하는 상인 (APIO17_merchant)	C++11	12 / 100	1094 ms	1280 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];

bool inQueue[N];
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];
}

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 s = 1; s <= n; s++){
        for(int i = 1; i <= n; i++){
            dist[i] = LLINF;
            trace[i] = 0;
            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;

            if (u != s && dist[s] >= dist[u] + cost[u][s] && a[u][s] != -1)
                return 1;

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

                if (dist[v] > dist[u] + cost[u][v] && a[u][v] != -1){
                    dist[v] = dist[u] + cost[u][v];
                    trace[v] = u;
                    if (!inQueue[v]){
                        qu.push(v);
                        inQueue[v] = 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:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  118 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  119 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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