제출 #57276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57276		gabrielsimoes	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	37 ms	2824 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 101, MAXM = 9901, MAXK = 1001;
const ll INF = 1e14;

int N, M, K;
vector<pii> g[MAXN], gt[MAXN];
int buy[MAXN][MAXK];
int sell[MAXN][MAXK];
ll dist[2][MAXN];

void dijkstra(int start, ll d[], vector<pii> g[]) {
    priority_queue<pair<int, ll>, vector<pair<int, ll>>, greater<pair<int, ll>>> q;

    for (int i = 1; i <= N; i++) d[i] = INF;

    q.push({0, start});
    d[start] = 0;

    while (!q.empty()) {
        ll dd; int cur;
        tie(dd, cur) = q.top();
        q.pop();

        if (dd > d[cur]) continue;

        // printf("dijkstra %d (%lld)\n", cur, d[cur]);

        for (pii p : g[cur]) {
            int nx = p.first;
            ll cost = p.second;

            // printf(" %d -> %d\n", cur, nx);

            if (dd + cost < d[nx]) {
                d[nx] = dd + cost;
                q.push({d[nx], nx});
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; i++) {
        for (int k = 1; k <= K; k++) {
            scanf("%d%d", &buy[i][k], &sell[i][k]);
        }
    }

    for (int i = 1,a,b,c; i <= M; i++) {
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back({b, c});
        gt[b].push_back({a, c});
    }

    dijkstra(1, dist[0], g);
    dijkstra(1, dist[1], gt);

    // for (int i = 1; i <= N; i++) {
    //     printf("%d<>%d: %lld %lld\n", 1, i, dist[0][i], dist[1][i]);
    // }

    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        for (int k = 1; k <= K; k++) {
            ll d = dist[0][i] + dist[1][i];
            if (buy[1][k] != -1 && sell[i][k] != -1 && d > 0) {
                ans = max(ans, ll(-buy[1][k] + sell[i][k])/d);
            }
        }
    }

    printf("%lld\n", ans);
}

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

merchant.cpp: In function 'int main()':
merchant.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &buy[i][k], &sell[i][k]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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