이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
const int MAX_N = 1e2 + 5;
const int MAX_K = 1e3 + 5;
int n, m, k, buy[MAX_K], sell[MAX_N], prof[MAX_N][MAX_N], dist[MAX_N][MAX_N];
long long last_prof[MAX_N], last_dist[MAX_N], ans;
struct data { int ind; long long prof, dist; };
bool operator < (const data &lhs, const data &rhs) { return lhs.dist > rhs.dist; }
void solve(int s)
{
memset(last_prof, 0xff, sizeof(last_prof));
memset(last_dist, 0x00, sizeof(last_dist));
std::priority_queue<data> q;
for (int i = 1; i <= n; ++i)
q.push({i, prof[s][i], dist[s][i]});
while (!q.empty())
{
data cur = q.top(); q.pop();
//printf("%d %lld %lld\n", cur.ind, cur.prof, cur.dist);
if (last_prof[cur.ind] * cur.dist < cur.prof * last_dist[cur.ind])
{
last_prof[cur.ind] = cur.prof;
last_dist[cur.ind] = cur.dist;
ans = std::max(ans, (cur.prof + prof[cur.ind][s]) / (cur.dist + dist[cur.ind][s]));
//printf("ans %lld\n", ans);
for (int i = 1; i <= n; ++i)
if (last_prof[i] * dist[cur.ind][i] <= prof[cur.ind][i] * last_dist[i])
q.push({i, cur.prof + prof[cur.ind][i], cur.dist + dist[cur.ind][i]});
}
}
}
int main()
{
memset(dist, 0x3f, sizeof(dist));
memset(buy, 0x7f, sizeof(buy));
memset(sell, 0x7f, sizeof(sell));
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i)
for (int j = 0; j < k; ++j)
{
int b, s; scanf("%d%d", &b, &s);
if (b != -1) { buy[i] = b; sell[i] = s; }
}
for (int i = 0; i < m; ++i)
{
int u, v, d; scanf("%d%d%d", &u, &v, &d);
dist[u][v] = d;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
dist[j][k] = std::min(dist[j][k], dist[j][i] + dist[i][k]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int p = 0; p < k; ++p)
prof[i][j] = std::max(prof[i][j], sell[j] - buy[i]);
for (int i = 1; i <= n; ++i)
solve(i);
printf("%lld\n", ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
merchant.cpp: In function 'int main()':
merchant.cpp:44:7: 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:48:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int b, s; scanf("%d%d", &b, &s);
~~~~~^~~~~~~~~~~~~~~~
merchant.cpp:53:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, d; scanf("%d%d%d", &u, &v, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |