제출 #316143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316143		phathnv	여행하는 상인 (APIO17_merchant)	C++11	12 / 100	95 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 i = 1; i <= n; i++){
        dist[i] = LLINF;
        trace[i] = 0;
        inQueue[i] = 0;
    }

    queue <int> qu;
    dist[1] = 0;
    qu.push(1);
    inQueue[1] = 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){
                //cerr << u << ' ' << v << endl;
                int cur = u;
                while (cur != 0){
                    if (cur == v)
                        return 1;
                    cur = trace[cur];
                    //cerr << cur << "->" << trace[cur] << endl;
                }
                //cerr << "done" << endl;
            }

            if (dist[v] > dist[u] + cost[u][v] && a[u][v] != -1){
                dist[v] = dist[u] + cost[u][v];
                trace[v] = u;
                //cerr << "trace[" << v << "]=" << u << endl;
                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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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