제출 #551457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551457		Ai7081	여행하는 상인 (APIO17_merchant)	C++17	0 / 100	39 ms	1952 KiB

merchant

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

const int N = 105;
const int K = 1005;

struct item{
    long x, t;
    item() {}
    item(long x, long t) : x(x), t(t) {}
    bool operator < (const item &o) const {
        if (!t) return true;
        if (!o.t) return false;
        if (x == 0 && o.x == 0) return t < o.t;
        return x*o.t < t*o.x;
    }
    bool operator > (const item &o) const {return !(*this < o);}
    item operator + (const item &o) {return item(x+o.x, t+o.t);}
    void operator += (const item &o) {x+=o.x; t+=o.t;}
};

struct node{
    item val;
    long v;
    bool operator < (const node &o) const {return val > o.val;}
};

long n, m, k, b[N][K], s[N][K];
item dis[N][N], out;
vector<pair<long, long>> adj[N];
priority_queue<node> pq;
bool mark[N];

void dfs(long root, long v, long t) {
    dis[root][v] = {0, t};
    mark[v] = true;
    for (int i=1; i<=k; i++) {
        if (root == v) break;
        if (b[root][i]!=-1 && s[v][i]!=-1) dis[root][v] = max(dis[root][v], {s[v][i]-b[root][i], t});
    }
    for (auto [to, cost] : adj[v]) if (!mark[to]) dfs(root, to, t+cost);
}

int main() {
    scanf(" %lld %lld %lld", &n, &m, &k);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=k; j++) scanf(" %lld", &b[i][j]);
        for (int j=1; j<=k; j++) scanf(" %lld", &s[i][j]);
    }
    while (m--) {
        long x, y, z;
        scanf(" %lld %lld %lld", &x, &y, &z);
        adj[x].push_back({y, z});

    }
    for (int i=1; i<=n; i++) fill_n(mark, N, false), dfs(i, i, 0);

//    for (int i=1; i<=n; i++) {
//        printf("dis %d : ", i);
//        for (int j=1; j<=n; j++) printf("(%lld %lld) ", dis[i][j].x, dis[i][j].t);
//        printf("\n");
//    }

    for (int s=1; s<=n; s++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) if (dis[i][s].t && dis[s][j].t) {
                dis[i][j] = max(dis[i][j], dis[i][s] + dis[s][j]);
            }
        }
    }

    for (int i=1; i<=n; i++) out = max(out, dis[i][i]);
//    printf("%lld %lld\n", out.x, out.t);
    printf("%lld", out.t ? out.x/out.t : 0);
    return 0;
}

/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

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

merchant.cpp: In function 'int main()':
merchant.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf(" %lld %lld %lld", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:48:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         for (int j=1; j<=k; j++) scanf(" %lld", &b[i][j]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:49:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         for (int j=1; j<=k; j++) scanf(" %lld", &s[i][j]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf(" %lld %lld %lld", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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